Advertisement
MinhNGUYEN2k4

Untitled

Mar 28th, 2021
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 200005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n, m, s;
  28. vector<int> a[N];
  29. bool draw, lose, win;
  30. bool znode[N];
  31. int vst[N][2];
  32. int trace[N];
  33.  
  34. void readfile()
  35. {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(0);cout.tie(0);
  38.     if (fopen(Task".inp","r"))
  39.     {
  40.         freopen(Task".inp","r",stdin);
  41.         //freopen(Task".out","w",stdout);
  42.     }
  43.     cin  >> n >> m;
  44.     for(int i=1; i<=n; i++)
  45.     {
  46.         int t,u;
  47.         cin >> t;
  48.         for(int j=1; j<=t; j++)
  49.         {
  50.             cin >> u;
  51.             a[i].pb(u);
  52.         }
  53.     }
  54.     cin >> s;
  55. }
  56.  
  57. bool dfs(int u, int steps)
  58. {
  59.     vst[u][steps%2]=1;
  60.     trace[steps] = u;
  61.     if (a[u].size()==0 && steps%2){
  62.         cout << "Win \n";
  63.         for(int i=0; i<=steps; i++)
  64.             cout << trace[i] << ' ';
  65.         return true;
  66.     }
  67.     for(auto v : a[u])
  68.     {
  69.         if (vst[v][1-steps%2]==1) draw=true;
  70.         else if (!vst[v][1-steps%2])
  71.         {
  72.             if (dfs(v,steps+1)) return true;
  73.         }
  74.     }
  75.     vst[u][steps%2]=2;
  76.     return false;
  77. }
  78.  
  79. void proc()
  80. {
  81.     draw=false;
  82.     if (!dfs(s,0))
  83.     {
  84.         if (draw) cout << "Draw";
  85.         else cout << "Lose";
  86.     }
  87. }
  88.  
  89. signed main()
  90. {
  91.     readfile();
  92.     proc();
  93.     return 0;
  94. }
  95.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement