fork download
copy 
  1. //It's all about what U BELIEVE
  2. #include<map>
  3. #include<set>
  4. #include<stack>
  5. #include<queue>
  6. #include<deque>
  7. #include<cmath>
  8. #include<bitset>
  9. #include<vector>
  10. #include<cstring>
  11. #include<stdio.h>
  12. #include<iostream>
  13. #include<algorithm>
  14. #define endl '\n'
  15. #define PI acos(-1)
  16. #define INF ~(1<<31)
  17. #define pb push_back
  18. #define pob pop_back
  19. #define wtm while(t--)
  20. #define wnm while(n--)
  21. #define MOD 1000000007
  22. #define lsone(Z) (Z&-Z)
  23. #define gcu getchar_unlocked
  24. #define allof(Z) Z.begin(),Z.end()
  25. #define rallof(Z) Z.rbegin(),Z.rend()
  26. #define mset(z,v) memset(z,v,sizeof(z))
  27. #define lne if(line)puts("");else line =1
  28. #define fo(s,y,z) for(int y=s ; y<(int)z ; y++)
  29. #define readf freopen("/home/ebram96/Desktop/in" , "r" , stdin);
  30. #define writef freopen("/home/ebram96/Desktop/out" , "w" , stdout);
  31. using namespace std;
  32. typedef unsigned long long ull;
  33. typedef pair<ull,ull> pairull;
  34. typedef pair<int,int> pairii;
  35. typedef vector<string> vstr;
  36. typedef deque<int> dqint;
  37. typedef set<ull> setull;
  38. typedef unsigned int ui;
  39. typedef queue<int> qint;
  40. typedef vector<int> vi;
  41. typedef set<int> seti;
  42. typedef long long ll;
  43. //int dx[]={-1,0,1, 0,-1,1, 1,-1};
  44. //int dy[]={ 0,1,0,-1, 1,1,-1,-1};
  45. int n , m , mars[100001][2];
  46. bool done[100001] , draw;
  47. vi adj[100001] , path;
  48. bool dfs(int node,int trn)
  49. {
  50. 	if(draw)return 0;
  51. 	if(done[node])
  52. 	{
  53. 		draw = 1;
  54. 		return 0;
  55. 	}
  56. 	if(~mars[node][trn])
  57. 		return mars[node][trn];
  58. 	path.pb(node);
  59. 	int sz = adj[node].size();
  60. 	if(sz == 0 && trn)
  61. 	{
  62. 		sz = path.size();
  63. 		printf("Win\n");
  64. 		fo(0,y,sz)
  65. 			printf("%d ",path[y]);
  66. 		return 1;
  67. 	}
  68. 	done[node] = 1;
  69. 	mars[node][trn] = 0;
  70. 	fo(0,y,sz)
  71. 		mars[node][trn] |= dfs(adj[node][y],!trn);
  72. 	path.pop_back();
  73. 	done[node] = 0;
  74. 	return mars[node][trn];
  75. }
  76. int main()
  77. {
  78. 	//readf
  79. 	scanf("%d %d",&n,&m);
  80. 	int v , sz;
  81. 	fo(1,u,n+1)
  82. 	{
  83. 		scanf("%d",&sz);
  84. 		while(sz--)
  85. 		{
  86. 			scanf("%d",&v);
  87. 			adj[u].pb(v);
  88. 		}
  89. 	}
  90. 	int s;
  91. 	scanf("%d",&s);
  92. 	mset(mars,-1);
  93. 	bool res = dfs(s,0);
  94. 	if(!res)
  95. 	{
  96. 		if(draw)printf("Draw");
  97. 		else puts("Lose");
  98. 	}
  99.  
  100. }
  101.  
Success #stdin #stdout 0s 6368KB
comments (?)
stdin
copy 
5 6
2 2 3
2 4 5
1 4
1 5
0
1
stdout
copy 
Win
1 2 4 5
https://ideone.com/kZvFal
language:
C++14 (gcc 8.3)
created:
6 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!