The problem is to finding a tree from a given graph.The main challenge is that the value of the node is not provided. So adjacency matrix can not be used to solve the problem. To define a tree for a directed graph : total edges = total vertices -1;root can not be more than one,
Year: 2015
599
#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; int parent[26]; int countNodes[26]; int getparent(int n) { if(parent[n]==n) return n; else return parent[n]=getparent(parent[n]); } void unite(int a,int b) { parent[getparent(a)]=getparent(b); } int main() { int t; string str; scanf("%d",&t); getchar(); while(t–) { str=""; for(int i=0;i<26;i++) { parent[i]=i; countNodes[i]=0; } while(getline(cin,str),str[0]!='*') { unite(str[1]-'A',str[3]-'A'); }
590
#include <iostream> #include <cstdio> #include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <queue> #include <cstdlib> #define INF 1000000000 #define ll long long using namespace std; int n,k; int flight_schedule_cost[11][11][40];//flight_schedule_cost[city][tocity][dayno]=cost of that day frm ct1 to cty 2 int periodOfCity[11][11]; ll dp[1010][15];//ll dp[day][citypath]; int kase=1; int costFromTheCity(int day,int startCity,int destination_city) { int schedulePeriod = periodOfCity[startCity][destination_city];
11734
#include <cstdio> #include <vector> #include <cstring> #include <algorithm> #include <iostream> using namespace std; int main() { int t,kase=1; string org,ans,tmp1,tmp2; scanf("%d",&t); getchar(); while(t–) { getline(cin,ans); getline(cin,org); if(org.size()==ans.size()) { bool f=0; for(int i=0;i<org.size();i++) { if(org[i]!=ans[i]) { f=1;break; } } if(f) printf("Case %d: Wrong Answer\n",kase++); else printf("Case %d: Yes\n",kase++); } else { tmp1="";tmp2=""; for(int i=0;i<org.size();i++) { if(org[i]!='
11934
Have some idea about Remainder Theorem, not necessary to solve the problem but it is good to revise some theorem. #include <iostream> #include <cstdio> #include <sstream> #include <string> #define ll long long using namespace std; int main() { int a,b,c,d,L; while(scanf("%d%d%d%d%d",&a,&b,&c,&d,&L)) { if(a==0 && b==0 && c==0 && d==0 && L==0) break; if(a==0 && b==0
11936
#include <iostream> #include <cstdio> #include <sstream> #include <string> using namespace std; int main() { int n,a,b,c; scanf("%d",&n); while(n–) { scanf("%d%d%d",&a,&b,&c); bool OK=1; if(a>=(b+c)) OK=0; if(b>=(a+c)) OK=0; if(c>=(a+b)) OK=0; if(OK) printf("OK\n"); else printf("Wrong!!\n"); } return 0; }
11610
To solve the problem indexes of the array are also needed to be updated and queried. #include <cstdio> #include <vector> #include <cstring> #include <algorithm> #include <iostream> using namespace std; struct RevPrime{ int reversePrime; int factorCount; }; int prime[1000001]; RevPrime arr[80000]; int Bit[2][80000]; vector<int> vb; int k=1; int reverse(int a) { int num=0; while(a) { num*=10;
10666
#include <iostream> #include <cstdio> using namespace std; //no of 1' indicate how many times at least it lost a game //no of 0' indicate how many times at least it lost a game //so if a team id does not contain a 0 it can be the last of the tournament at it pessimist decision
10487
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <iostream> //#include <cstdlib> #define ll long long using namespace std; int a[1010]; vector<int> sum; int binarySearch(int num,int lw,int hi) { if(hi-lw==1) { int diff1 = abs(num-sum[lw]); int diff2 = abs(num-sum[hi]); if(diff1<diff2) return sum[lw]; else return sum[hi]; } int mid=(lw+hi)>>1; if(num<=sum[mid]) return binarySearch(num,lw,mid); else return binarySearch(num,mid,hi); return
1428
The problem can be solved using Binary Indexed tree or Fenwick tree. #include <cstdio> #include <queue> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <string> #define SZ 100000+5 #define ll long long using namespace std; int arr[SZ]; ll Left[SZ],Right[SZ],sum[SZ]; int mx; ll Cumulative(int idx) { ll value=0; while(idx>0) { value += sum[idx]; idx -=