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 dp[N][20];
  37.  
  38. int dfs(int s)
  39. {
  40. 	if(mark[s]!=0)return 0;
  41.  
  42. 	mark[s]=1;
  43. 	d[s]=h[s];
  44.  
  45. 	int pow=2;
  46. 	FOR(i,1,20)
  47. 	{
  48. 			if(h[s]-pow<1)break;
  49. 			dp[s][i]=dp[dp[s][i-1]][i-1];
  50. 			pow*=2;
  51. 	}
  52.  
  53. 	FOR(i,0,v[s].size()-1)
  54. 	{
  55. 		if(mark[v[s][i]]==0)
  56. 		{
  57.  
  58. 		dp[v[s][i]][0]=s;//lca intial
  59.  
  60. 		h[v[s][i]]=h[s]+1;
  61. 		dfs(v[s][i]);
  62. 		d[s]=min(d[s],d[v[s][i]]);
  63.  
  64. 		if(d[v[s][i]]>h[s])
  65. 		{
  66. 		ce[ppi(s,v[s][i])]=1;
  67. 		ce[ppi(v[s][i],s)]=1;
  68. 		}
  69. 		else
  70. 		{
  71. 		ce[ppi(s,v[s][i])]=0;
  72. 		ce[ppi(v[s][i],s)]=0;
  73. 		}
  74.  
  75. 		}
  76. 		else
  77. 		{
  78. 			if(dp[s][0]!=v[s][i])
  79. 			{
  80. 				d[s]=min(d[s],d[v[s][i]]);
  81. 			}
  82. 		}
  83.  
  84. 	}
  85.  
  86. 	if(d[s]>=h[s])
  87. 	{
  88. 		markv[s]=1;
  89. 	}
  90. 	return 0;
  91. }
  92.  
  93. int sh(int a,int b)
  94. {
  95. 	if(h[b]<h[a])swap(a,b);
  96. 	if(h[a]==h[b])return  b;
  97.  
  98. 	int k=0,pow=1;
  99.  
  100. 	while(h[b]-pow>=h[a])
  101. 	{
  102. 	pow*=2;
  103. 	k++;
  104. 	}
  105. 	k--;
  106. 	FORD(i,k,0)
  107. 	{
  108. 		if(h[dp[b][i]]>=h[a])
  109. 		{
  110. 			b=dp[b][i];
  111. 		}
  112. 	}
  113. 	return b;
  114. }
  115.  
  116. int lca(int a,int b)
  117. {
  118. 	if(h[a]>h[b])swap(a,b);
  119.  
  120. 	b=sh(a,b);
  121. 	if(a==b)return a;
  122. 	int k=0,pow=1;
  123.  
  124. 	while(h[b]-pow>0)
  125. 	{pow*=2;
  126. 	k++;
  127. 	}
  128. 	k--;
  129.  
  130. 	FORD(i,k,0)
  131. 	{
  132. 		if(dp[a][k]!=dp[b][k])
  133. 		{
  134. 			a=dp[a][k];
  135. 			b=dp[b][k];
  136. 		}
  137. 	}
  138.  
  139. 	return dp[a][0];
  140. }
  141.  
  142. int q1(int a,int b,int x,int y)
  143. {
  144. 	if(ce[ppi(x,y)]==0)return 1;
  145.  
  146. 	if(h[x]<h[y])swap(x,y);
  147. 	int s1=-1,s2=-1;
  148. 	if(lca(x,a)==x)s1=1;
  149. 	if(lca(x,b)==x)s2=1;
  150.  
  151.  
  152. 	if(s1*s2==1)return 1;
  153. 	else
  154. 	return 0;
  155. }
  156.  
  157. int q2(int a,int b,int c)
  158. {
  159. 	if(markv[c]==0)return 1;
  160.  
  161. 	if(lca(a,c)==c&&lca(b,c)==lca(a,b))return 0;
  162. 	else
  163. 	if(lca(b,c)==c&&lca(a,c)==lca(a,b))return 0;
  164.  
  165. 	return 1;
  166.  
  167. }
  168.  
  169. int main()
  170. {
  171. 	int n,m;
  172.  
  173. 	scanf("%d%d",&n,&m);
  174.  
  175. 	FOR(i,0,m-1)
  176. 	{
  177. 		int x,y;
  178. 		scanf("%d%d",&x,&y);
  179. 		v[x].pb(y);
  180. 		v[y].pb(x);	
  181. 	}
  182.  
  183.  
  184. 	dp[1][0]=0;
  185. 	h[1]=1;
  186. 	dfs(1);
  187.  
  188.  
  189. 	int q;
  190. 	scanf("%d",&q);
  191.  
  192. 	//cout<<endl<<d[2]<<endl<<markv[2]<<endl;
  193. 	while(q--)
  194. 	{
  195. 		int t;
  196. 		scanf("%d",&t);
  197. 		int a,b;
  198. 		scanf("%d%d",&a,&b);
  199. 		if(t==1)
  200. 		{
  201. 			int x,y;
  202. 			scanf("%d%d",&x,&y);
  203. 			//cout<<endl<<ce[ppi(x,y)]<<endl;
  204. 			if(q1(a,b,x,y))
  205. 			{
  206. 				printf("da\n");
  207. 			}
  208. 			else
  209. 			{printf("ne\n");
  210. 			}
  211. 		}
  212. 		else
  213. 		{
  214. 			int c;
  215. 			scanf("%d",&c);
  216. 			if(q2(a,b,c))
  217. 			{
  218. 				printf("da\n");
  219. 			}
  220. 			else
  221. 			{printf("ne\n");
  222. 			}
  223. 		}
  224. 	}
  225.  
  226. 	return 0;
  227.  
  228. }
Success #stdin #stdout 0s 14016KB
comments (?)
stdin
copy 
13 15
1 2
2 3
3 5
2 4
4 6
2 6
1 4
1 7
7 8
7 9
7 10
8 11
8 12
9 12
12 13
5
1 5 13 1 2
1 6 2 1 4
1 13 6 7 8
2 13 6 7
2 13 6 8
stdout
copy 
da
da
da
ne
da
https://ideone.com/ljHSna
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!