fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<functional>
  4. #include<algorithm>
  5. #include<math.h>
  6. #include<limits.h>
  7.  
  8. #include<set>
  9. #include<vector>
  10. #include<map>
  11. #include<queue>
  12. #include<stack>
  13. #include<deque>
  14.  
  15. #include<cstring>
  16. #include<string>
  17.  
  18.  
  19. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  20. #define FORD(i,a,b) for(int i=a;i>=b;i--)
  21. #define pb push_back 
  22. #define lli long long int
  23. #define mod1 1000000007
  24. #define mod2 1000000009
  25. #define ppi pair<int,int>
  26. #define tr(a,it) for(typeof(a.begin()) it=a.begin();it!=a.end();it++)
  27. #define N 100001
  28.  
  29. using namespace std;
  30.  
  31. vector<int>v[N];
  32. map< ppi ,int >ce;
  33. int mark[N]={0};
  34. int d[N],h[N];
  35. int markv[N]={0};
  36. int c=1;
  37. int timer=1;
  38. int first[N],last[N];
  39. int dp[N][20];
  40.  
  41. int dfs(int s)
  42. {
  43. 	if(mark[s]!=0)return 0;
  44.  
  45. 	mark[s]=c;
  46. 	first[s]=timer;
  47. 	timer++;
  48. 	d[s]=h[s];
  49.  
  50. 	int pow=2;
  51. 	FOR(i,1,20)
  52. 	{
  53. 			if(h[s]-pow<1)break;
  54. 			dp[s][i]=dp[dp[s][i-1]][i-1];
  55. 			pow*=2;
  56. 	}
  57.  
  58. 	FOR(i,0,v[s].size()-1)
  59. 	{
  60. 		if(mark[v[s][i]]==0)
  61. 		{
  62.  
  63. 		dp[v[s][i]][0]=s;//lca intial
  64.  
  65. 		h[v[s][i]]=h[s]+1;
  66. 		dfs(v[s][i]);
  67. 		d[s]=min(d[s],d[v[s][i]]);
  68.  
  69. 		if(d[v[s][i]]>h[s])
  70. 		{
  71. 		ce[ppi(s,v[s][i])]=1;
  72. 		ce[ppi(v[s][i],s)]=1;
  73. 		}
  74. 		else
  75. 		{
  76. 		ce[ppi(s,v[s][i])]=0;
  77. 		ce[ppi(v[s][i],s)]=0;
  78. 		}
  79.  
  80. 		}
  81. 		else
  82. 		{
  83. 			if(dp[s][0]!=v[s][i])
  84. 			{
  85. 				d[s]=min(d[s],d[v[s][i]]);
  86. 			}
  87. 		}
  88.  
  89. 	}
  90.  
  91. 	if(d[s]>=h[s])
  92. 	{
  93. 		markv[s]=1;
  94. 	}
  95.  
  96. 	last[s]=timer;
  97.  
  98. 	return 0;
  99. }
  100.  
  101. int sh(int a,int b)
  102. {
  103. 	if(h[b]<h[a])swap(a,b);
  104. 	if(h[a]==h[b])return  b;
  105.  
  106. 	int k=0,pow=1;
  107.  
  108. 	while(h[b]-pow>=h[a])
  109. 	{
  110. 	pow*=2;
  111. 	k++;
  112. 	}
  113. 	k--;
  114. 	FORD(i,k,0)
  115. 	{
  116. 		if(h[dp[b][i]]>=h[a])
  117. 		{
  118. 			b=dp[b][i];
  119. 		}
  120. 	}
  121. 	return b;
  122. }
  123.  
  124. int lca(int a,int b)
  125. {
  126. 	if(h[a]>h[b])swap(a,b);
  127.  
  128. 	b=sh(a,b);
  129. 	if(a==b)return a;
  130. 	int k=0,pow=1;
  131.  
  132. 	while(h[b]-pow>0)
  133. 	{pow*=2;
  134. 	k++;
  135. 	}
  136. 	k--;
  137.  
  138. 	FORD(i,k,0)
  139. 	{
  140. 		if(dp[a][k]!=dp[b][k])
  141. 		{
  142. 			a=dp[a][k];
  143. 			b=dp[b][k];
  144. 		}
  145. 	}
  146.  
  147. 	return dp[a][0];
  148. }
  149.  
  150. int q1(int a,int b,int x,int y)
  151. {
  152. 	if(mark[a]!=mark[b])return 0;
  153. 	if(ce[ppi(x,y)]==0)return 1;
  154.  
  155. 	if(h[x]<h[y])swap(x,y);
  156. 	int s1=-1,s2=-1;
  157. 	if(first[x]<=first[a]&&first[a]<=last[x])s1=1;
  158. 	if(first[x]<=first[b]&&first[b]<=last[x])s2=1;
  159.  
  160. 	if(s1*s2==1)return 1;
  161. 	else
  162. 	return 0;
  163. }
  164.  
  165. int q2(int a,int b,int c)
  166. {
  167. 	if(mark[a]!=mark[b])return 0;
  168. 	if(markv[c]==0)return 1;
  169.  
  170. 	if(lca(a,c)==c&&lca(b,c)==lca(a,b))return 0;
  171. 	else
  172. 	if(lca(b,c)==c&&lca(a,c)==lca(a,b))return 0;
  173.  
  174. 	return 1;
  175.  
  176. }
  177.  
  178. int main()
  179. {
  180. 	int n,m;
  181.  
  182. 	scanf("%d%d",&n,&m);
  183.  
  184. 	FOR(i,0,m-1)
  185. 	{
  186. 		int x,y;
  187. 		scanf("%d%d",&x,&y);
  188. 		v[x].pb(y);
  189. 		v[y].pb(x);	
  190. 	}
  191.  
  192. 	FOR(i,1,n)
  193. 	{
  194. 		if(mark[i]==0)
  195. 		{
  196. 			dp[i][0]=0;
  197. 		h[i]=1;
  198. 		dfs(i);
  199. 		c++;
  200. 		}
  201. 	}
  202. 	//cout<<ce[ppi(1,2)]<<endl;
  203.  
  204. 	int q;
  205. 	scanf("%d",&q);
  206.  
  207. 	//cout<<endl<<d[2]<<endl<<markv[2]<<endl;
  208. 	while(q--)
  209. 	{
  210. 		int t;
  211. 		scanf("%d",&t);
  212. 		int a,b;
  213. 		scanf("%d%d",&a,&b);
  214. 		if(t==1)
  215. 		{
  216. 			int x,y;
  217. 			scanf("%d%d",&x,&y);
  218. 			//cout<<endl<<ce[ppi(x,y)]<<endl;
  219. 			if(q1(a,b,x,y))
  220. 			{
  221. 				printf("da\n");
  222. 			}
  223. 			else
  224. 			{printf("ne\n");
  225. 			}
  226. 		}
  227. 		else
  228. 		{
  229. 			scanf("%d",&c);
  230. 			if(q2(a,b,c))
  231. 			{
  232. 				printf("da\n");
  233. 			}
  234. 			else
  235. 			{printf("ne\n");
  236. 			}
  237. 		}
  238. 	}
  239.  
  240. 	return 0;
  241.  
  242. }
  243.  
Runtime error #stdin #stdout 0s 14744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/v29X7x
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

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!