fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=5000+10;
  27. const int NUM=1000000+10;
  28.  
  29. int n,m,k;
  30. int begin[MAX],next[MAX*2],t[MAX*2],tot;
  31. int A[NUM],B[NUM],ans[NUM],D[NUM];
  32. vector<int> query[MAX];
  33.  
  34. void add(int a,int b)
  35. {
  36. 	t[++tot]=b;
  37. 	next[tot]=begin[a];
  38. 	begin[a]=tot;
  39. }
  40.  
  41. int q[NUM*2],kind[NUM*2],d[NUM][2];
  42. int head,end;
  43.  
  44. void BFS(int u)
  45. {
  46. 	int i;
  47. 	head=end=0;
  48. 	REP(i,1,n)
  49. 		d[i][0]=d[i][1]=-1;
  50. 	d[u][0]=0;
  51. 	q[end]=u;
  52. 	kind[end++]=0;
  53.  
  54. 	while(head<end)
  55. 	{
  56. 		int u=q[head];
  57. 		int p=kind[head++];
  58.  
  59. 		for(i=begin[u];i;i=next[i])
  60. 		{
  61. 			int v=t[i];
  62. 			if(d[v][p^1]==-1)
  63. 			{
  64. 				d[v][p^1]=d[u][p]+1;
  65. 				q[end]=v;
  66. 				kind[end++]=p^1;
  67. 			}
  68. 		}
  69. 	}
  70.  
  71. 	for(i=0;i<(int)query[u].size();++i)
  72. 	{
  73. 		int t=query[u][i];
  74. 		if(B[t]==u && D[t]>=1 && !begin[u])
  75. 		{
  76. 			ans[t]=0;
  77. 			continue;
  78. 		}
  79. 		ans[t]=( d[B[t]][D[t]%2]<=D[t] && d[B[t]][D[t]%2]!=-1 );
  80. 	}
  81. }
  82.  
  83. int main()
  84. {
  85. #ifndef ONLINE_JUDGE
  86. //	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  87. #endif
  88. 	int i,a,b;
  89. 	scanf("%d%d%d",&n,&m,&k);
  90. 	REP(i,1,m)
  91. 	{
  92. 		scanf("%d%d",&a,&b);
  93. 		add(a,b);
  94. 		add(b,a);
  95. 	}
  96. 	REP(i,1,k)
  97. 	{
  98. 		scanf("%d%d%d",&A[i],&B[i],&D[i]);
  99. 		query[A[i]].pb(i);
  100. 	}
  101. 	REP(i,1,n)
  102. 		BFS(i);
  103. 	REP(i,1,k)
  104. 		if(ans[i])
  105. 			printf("TAK\n");
  106. 		else printf("NIE\n");
  107. 	return 0;
  108. }
  109.  
Success #stdin #stdout 0s 42656KB
comments (?)
stdin
copy 
8 7 4
1 2
2 3
3 4
5 6
6 7
7 8
8 5
2 3 1
1 4 1
5 5 8
1 8 10
stdout
copy 
TAK
NIE
TAK
NIE
https://ideone.com/QwYNAl
language:
C++ (gcc 8.3)
created:
10 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!