fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i,a,b) for(int i=a;i<b;i++)
  4. #define REP(i,b) FOR(i,0,b)
  5. #define PB push_back
  6.  
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10.  
  11. inline int Pack(int x,bool b){
  12. 	return (x<<1)+b;
  13. }
  14.  
  15. inline int Idx(int x){
  16. 	return x>>1;
  17. }
  18.  
  19. inline int Flag(int x){
  20. 	return x&1;
  21. }
  22.  
  23. inline int Not(int x){
  24. 	return x^1;
  25. }
  26.  
  27. struct TwoSAT{
  28. 	static const int maxN = 100000*2;
  29. 	static const int maxM = 100000*2;
  30. 	int m,edge[maxM][2];
  31. 	TwoSAT():m(0),t(-1){
  32. 		memset(last,-1,sizeof(last));
  33. 		memset(pushed,false,sizeof(pushed));
  34. 	}
  35. 	void Add(int x,int y){
  36. 		edge[m][0]=Not(x);
  37. 		edge[m++][1]=y;
  38. 		edge[m][0]=Not(y);
  39. 		edge[m++][1]=x;
  40. 	}
  41. 	int t,last[maxN];
  42. 	int s,use[maxN];
  43. 	void Mark(int x){
  44. 		if(last[x]<t){
  45. 			last[x]=t;
  46. 			use[s++]=x;
  47. 		}
  48. 	}
  49. 	vector<int> graph[maxN];
  50. 	int sSize,sBuf[maxN];
  51. 	void Push(int x){
  52. 		sBuf[sSize++]=x;
  53. 	}
  54. 	int Pop(){
  55. 		return sBuf[--sSize];
  56. 	}
  57. 	bool pushed[maxN];
  58. 	int num,ord[maxN],low[maxN],group[maxN],cmps;
  59. 	void scc(int v){
  60. 		Push(v);
  61. 		pushed[v]=true;
  62. 		ord[v]=low[v]=num++;
  63. 		for(auto i:graph[v]){
  64. 			if(ord[i]==-1){
  65. 				scc(i);
  66. 				low[v]=min(low[v],low[i]);
  67. 			}else if(pushed[i])
  68. 				low[v]=min(low[v],ord[i]);
  69. 		}
  70. 		if(ord[v]==low[v]){
  71. 			while(1){
  72. 				int x=Pop();
  73. 				pushed[x]=false;
  74. 				group[x]=cmps;
  75. 				if(x==v)
  76. 					break;
  77. 			}
  78. 			cmps++;
  79. 		}
  80. 	}
  81. 	bool SAT(int b,int e){
  82. 		b*=2;
  83. 		e*=2;
  84. 		s=0;
  85. 		t++;
  86. 		FOR(i,b,e){
  87. 			Mark(edge[i][0]);
  88. 			Mark(edge[i][1]);
  89. 		}
  90. 		REP(_,s){
  91. 			int i=use[_];
  92. 			graph[i].clear();
  93. 			ord[i]=low[i]=-1;
  94. 		}
  95. 		FOR(i,b,e)
  96. 			graph[edge[i][0]].PB(edge[i][1]);
  97. 		sSize=0;
  98. 		num=0;
  99. 		cmps=0;
  100. 		REP(_,s){
  101. 			int i=use[_];
  102. 			if(ord[i]==-1)
  103. 				scc(i);
  104. 		}
  105. 		REP(_,s){
  106. 			int i=use[_];
  107. 			if(group[i]==group[Not(i)])
  108. 				return false;
  109. 		}
  110. 		return true;
  111. 	}
  112. } tSat;
  113.  
  114. int read(){
  115. 	int i;
  116. 	scanf("%d",&i);
  117. 	return i;
  118. }
  119.  
  120. const int maxN=100000;
  121. const int maxM=100000;
  122. int s[maxM][2],group[maxM*2],ch[maxM*2][2],w[maxM*2];
  123. vector<int> member[maxM*2];
  124. bool ans[maxM*2];
  125.  
  126. void dfs(int v,int l,int r,int p){
  127. 	if(l+1==r)
  128. 		return;
  129. 	if(p==-1){
  130. 		int a=l,b=r+1;
  131. 		while(b-a>=2){
  132. 			int mid=(a+b)/2;
  133. 			if(tSat.SAT(l,mid))
  134. 				a=mid;
  135. 			else
  136. 				b=mid;
  137. 		}
  138. 		p=a;
  139. 	}
  140. 	ans[v]=r<=p;
  141. 	dfs(ch[v][0],l,l+w[v],p);
  142. 	if(r<=p)
  143. 		dfs(ch[v][1],l+w[v],r,p);
  144. 	else
  145. 		dfs(ch[v][1],l+w[v],r,-1);
  146. }
  147.  
  148. int main(){
  149. 	read();
  150. 	int m=read();
  151. 	REP(i,m){
  152. 		int a=read(),b=read();
  153. 		s[i][0]=Not(Pack(abs(a)-1,a>0));
  154. 		s[i][1]=Not(Pack(abs(b)-1,b>0));
  155. 	}
  156. 	REP(i,m)
  157. 		member[i].PB(i);
  158. 	FOR(i,m,m*2-1){
  159. 		int a=read()-1,b=read()-1;
  160. 		if(member[a].size()<member[b].size())
  161. 			swap(a,b);
  162. 		ch[i][0]=a;
  163. 		ch[i][1]=b;
  164. 		w[i]=member[a].size();
  165. 		swap(member[i],member[a]);
  166. 		copy(member[b].begin(),member[b].end(),back_inserter(member[i]));
  167. 	}
  168. 	for(auto i:member[m*2-2])
  169. 		tSat.Add(s[i][0],s[i][1]);
  170. 	dfs(m*2-2,0,m,-1);
  171. 	FOR(i,m,m*2-1)
  172. 		printf(ans[i]?"Possible\n":"Impossible\n");
  173. }
Runtime error #stdin #stdout 1.1s 18696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GZrgsZ
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!