0
Your rating: None

CodeChef submission 130761 (C++ 4.0.0-8)

CodeChef submission 130761 (C++ 4.0.0-8) plaintext list. Status: WA, problem J6, contest NOV09. By srirams (sriram), 2009-11-11 12:40:12.
  1. using namespace std;
  2. #include <vector>
  3. #include <list>
  4. #include <map>
  5. #include <set>
  6. #include <deque>
  7. #include <queue>
  8. #include <stack>
  9. #include <bitset>
  10. #include <algorithm>
  11. #include <functional>
  12. #include <numeric>
  13. #include <utility>
  14. #include <sstream>
  15. #include <iostream>
  16. #include <iomanip>
  17. #include <cstdio>
  18. #include <cmath>
  19. #include <cstdlib>
  20. #include <ctime>
  21. #define REP(i,n) for(i=0;i<n;i++)
  22. #define FOR(i,A,n) for(i=A;i<n;i++)
  23. #define sz(c) (signed int) c.size()
  24. #define pb(c) push_back(c)
  25. #define INF (int) 1e9
  26. #define all(c) c.begin(),c.end()
  27. #define GI(t) scanf("%d",&t);
  28. typedef long long LL;
  29. typedef vector<int> VI;
  30. typedef pair<int,int> PII;
  31.  
  32. struct Person {
  33. 	vector<int>evi;  // Evidence Nos 
  34. 	int status;      // indicates involvement/non-involvement/uncertain
  35. 	bool visit;
  36. };
  37.  
  38. typedef struct Person person;
  39.  
  40. #define inv 1
  41. #define ninv -1
  42. #define not_sure 0
  43.  
  44. int DFS(vector<person>& v,vector<PII>& R,int i);
  45.  
  46. int main() {
  47. 	int i,j;
  48. 	int n,k;
  49. 	int t;
  50. 	GI(t);
  51. 	int l,m;
  52. 	PII s;
  53. 	int p,q;
  54. 	bool f1,f2;
  55. 	while(t--) {
  56. 		GI(n);GI(k);
  57. 		if(k==0) {printf("MULTIPLE\n");continue;}      // trivial case - no evidence
  58. 		vector<person>v;
  59. 		vector<PII>R;
  60. 		person P;
  61. 		map<PII,int>M;
  62. 		int flag=0;
  63. 		// Initialise the N persons
  64. 		REP(i,n) {
  65. 			P.status=not_sure;
  66. 			P.visit=false;	
  67. 			v.pb(P);
  68. 		}
  69. 		REP(i,k) {
  70. 			GI(p);GI(q);
  71. 			s.first=p;s.second=q;
  72. 			R.pb(s);     // Store the evidence, we may need it later
  73. 			l=abs(p);
  74. 			m=abs(q);
  75. 			f1=true;
  76. 			f2=true;
  77. 			// Check for clinching evidence
  78. 			if(l==m) {  // same person 
  79. 				if(p==q) { // true evidence
  80. 					if((v[l-1].status==inv && p<0) || (v[l-1].status==ninv && p>0)) {
  81. 						printf("CONFLICT\n");
  82. 						flag=1;
  83. 						break;
  84. 					}
  85. 					else {
  86. 						if(p>0) v[l-1].status=inv;
  87. 						else v[l-1].status=ninv;
  88. 					}
  89. 				}
  90. 			}
  91. 			else {  // Different person
  92. 				// Test each part separately
  93. 				if((v[l-1].status==inv && p<0) || (v[l-1].status==ninv && p>0)) {
  94.                                         // 1st part is false
  95.                                         f1=false;
  96.                                 }
  97.                                 if((v[m-1].status==inv && q<0) || (v[m-1].status==ninv && q>0)) {
  98.                                         // 2nd part is false;
  99.                                         f2=false;
  100.                                 }
  101.                                 if(!f1 && !f2) {
  102. 					printf("CONFLICT\n");
  103.                                         flag=1;
  104.                                         break;
  105.                                 }
  106.                                 if(!f1) {
  107.                                         // 2nd part is true
  108.                                         v[m-1].status=(q>0)?inv:ninv;
  109. 					continue;
  110.                                 }
  111.                                 if(!f2) {
  112.                                         // 1st part is true
  113.                                         v[l-1].status=(p>0)?inv:ninv;
  114. 					continue;
  115.                                 }
  116. 				// Check for boolean table
  117. 				// Consider 2 vars A&B, the possible values are (00,01,10,11)
  118. 				// 0 is = not involved
  119. 				// For 00,score =1,01 score=2,10 score=4,11 score =8
  120. 				// Store the score in map<PII>, pair shud be unique,so make it ordered
  121. 				if(l<m) {
  122. 					s.first=l;s.second=m;
  123. 				}
  124. 				else {
  125. 					s.first=m;s.second=l;
  126. 					swap(p,q);
  127. 				}
  128. 				if(p>0) {
  129. 					if(q>0) 
  130. 					M[s]+=8;
  131. 					else M[s]+=4;
  132. 				}
  133. 				else {
  134. 					if(q>0) 
  135. 					M[s]+=2;
  136. 					else M[s]+=1;
  137. 				}
  138.  
  139.  
  140. 				// We dont have clinching evidence now,so store it for later use
  141. 				v[l-1].evi.pb(i);
  142. 				v[m-1].evi.pb(i);
  143.  
  144. 			}
  145. 		}
  146. 		if(flag) continue;
  147. 		
  148. 		// Get answer from boolean table if possible 
  149. 		map<PII,int>::iterator it;
  150. 		for(it=M.begin();it!=M.end();it++) {
  151. 			s=it->first;
  152. 			//cout<<s.first<<" "<<s.second<<" "<<M[s]<<endl;
  153. 			// 2 of the values in the table are avail,so we can determine l or m for some scores.
  154. 			if(M[s]==3) {
  155. 				l=s.first;
  156. 				if(v[l-1].status==inv) {
  157.                                         printf("CONFLICT\n");
  158.                                         flag=1;
  159.                                         break;
  160.                                 }
  161.                                 else
  162.                                 v[l-1].status=ninv;
  163. 			}
  164. 			if(M[s]==12) {
  165. 				l=s.first;
  166. 				if(v[l-1].status==ninv) {
  167.                                         printf("CONFLICT\n");
  168.                                         flag=1;
  169.                                         break;
  170.                                 }
  171.                                 else
  172.                                 v[l-1].status=inv;
  173.  
  174. 			}	
  175. 			if(M[s]==5) {
  176. 				m=s.second;
  177. 				if(v[m-1].status==inv) {
  178.                                         printf("CONFLICT\n");
  179.                                         flag=1;
  180.                                         break;
  181.                                 }
  182.                                 else
  183.                                 v[m-1].status=ninv;
  184. 			}
  185. 			if(M[s]==10) {
  186. 				m=s.second;
  187. 				if(v[m-1].status==ninv) {
  188.                                         printf("CONFLICT\n");
  189.                                         flag=1;
  190.                                         break;
  191.                                 }
  192.                                 else
  193.                                 v[m-1].status=inv;
  194.  
  195. 			}
  196.  
  197. 			// 3 values in the table are avail, so we can determine value of l & m uniquely.
  198. 			if(M[s]==7) {
  199. 				l=s.first;m=s.second;
  200. 				if(v[l-1].status==inv || v[m-1].status==inv) {
  201. 					printf("CONFLICT\n");
  202. 					flag=1;
  203. 					break;
  204. 				}
  205. 				else {
  206. 					v[l-1].status=ninv;
  207. 					v[m-1].status=ninv;
  208. 				}
  209. 			}
  210. 			if(M[s]==11) {
  211. 				l=s.first;m=s.second;
  212.                                 if(v[l-1].status==inv || v[m-1].status==ninv) {
  213.                                         printf("CONFLICT\n");
  214.                                         flag=1;
  215.                                         break;
  216.                                 }
  217.                                 else {
  218.                                         v[l-1].status=ninv;
  219.                                         v[m-1].status=inv;
  220.                                 }
  221.  
  222. 			}
  223. 			if(M[s]==13) {
  224. 				l=s.first;m=s.second;
  225.                                 if(v[l-1].status==ninv || v[m-1].status==inv) {
  226.                                         printf("CONFLICT\n");
  227.                                         flag=1;
  228.                                         break;
  229.                                 }
  230.                                 else {
  231.                                         v[l-1].status=inv;
  232.                                         v[m-1].status=ninv;
  233.                                 }
  234.  
  235. 			}
  236. 			if(M[s]==14) {
  237. 				l=s.first;m=s.second;
  238.                                 if(v[l-1].status==ninv || v[m-1].status==ninv) {
  239.                                         printf("CONFLICT\n");
  240.                                         flag=1;
  241.                                         break;
  242.                                 }
  243.                                 else {
  244.                                         v[l-1].status=inv;
  245.                                         v[m-1].status=inv;
  246.                                 }
  247.  
  248. 			}
  249. 			// All 4 values available, no solution possible
  250. 			if(M[s]==15) {
  251. 				printf("CONFLICT\n");
  252. 				flag=1;
  253. 				break;
  254. 			}
  255. 		}
  256. 		if(flag) continue;
  257. 		
  258. 		// Ok, now we have some results, we need more
  259. 		// DFS seems to be good
  260. 		REP(i,n) {
  261. 			if((v[i].status==inv || v[i].status==ninv) && v[i].visit==false) {
  262. 				int ret=DFS(v,R,i);
  263. 				if(ret==-1) {
  264. 					flag=1;
  265. 					break;
  266. 				}
  267. 			}
  268. 		}
  269.  
  270.  
  271. 		if(flag) continue;
  272.  
  273. 		REP(i,n) {
  274. 			if(v[i].status==not_sure) {
  275. 				flag=1;
  276. 				printf("MULTIPLE\n");
  277. 				break;
  278. 			}
  279. 			
  280. 		}
  281. 		if(!flag) printf("UNIQUE\n") ;
  282. 	}
  283. 	return 0;
  284. }
  285.  
  286. int DFS(vector<person>& v,vector<PII>& R,int i) {
  287. 	int j;
  288. 	PII s;
  289. 	int l,m,p,q;
  290. 	int flag=0;
  291. 	int ret=0;
  292. 	REP(j,sz(v[i].evi)) {
  293. 		s=R[v[i].evi[j]];
  294. 		p=s.first;q=s.second;
  295. 		l=abs(p);m=abs(q);
  296. 		bool f1=true,f2=true;	
  297. 		if((v[l-1].status==inv && p<0) || (v[l-1].status==ninv && p>0)) {
  298. 	                // 1st part is false
  299.                         f1=false;
  300.                 }
  301.                 if((v[m-1].status==inv && q<0) || (v[m-1].status==ninv && q>0)) {
  302.          	       // 2nd part is false;
  303.                        f2=false;
  304.                 }
  305.                 if(!f1 && !f2) {
  306.                		printf("CONFLICT\n");
  307.                         flag=1;
  308.                         break;
  309.                 }
  310.                 if(!f1) {
  311.                 	// 2nd part is true
  312. 			if(v[m-1].status==not_sure) {
  313.                         	v[m-1].status=(q>0)?inv:ninv;
  314. 				if(v[m-1].visit==false) {
  315. 					ret=DFS(v,R,m-1);
  316. 					if(ret==-1) break;
  317. 				}
  318. 			}
  319.                 }
  320.                 if(!f2) {
  321.                 	// 1st part is true
  322. 			if(v[l-1].status==not_sure) {
  323.                         	v[l-1].status=(p>0)?inv:ninv;
  324. 				if(v[l-1].visit==false) {
  325. 					ret=DFS(v,R,l-1);
  326. 					if(ret==-1) break;
  327. 				}
  328. 			}
  329.                 }
  330. 		//cout<<v[l-1].status<<" "<<v[m-1].status<<endl;
  331. 	
  332. 	}	
  333. 	v[i].visit=true;
  334. 	if(flag==1 || ret==-1) return -1;
  335. 	else return 0;
  336. }
  337.

Comments