Submission #583900

#	Time	Username	Problem	Language	Result	Execution time	Memory
583900		MrDeboo	Sleepy game (innopolis2018_final_D)	C++17	100 / 100	134 ms	20536 KiB

D

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
vector<int>vct[100001];
vector<int>tcv[100001];
pair<int,int>vis[100001][2];
bool viss[100001];
bool vis2[100001];
bool dfs1(int in){
	if(viss[in])return 1;
	viss[in]=1;
	bool bol=0;
	for(auto &i:vct[in]){
		if(!vis2[i]&&dfs1(i))bol=1;
	}
	viss[in]=0;
	vis2[in]=1;
	return bol;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for(int i=0;i<100001;i++){
        vis[i][0]={-1,-1};
        vis[i][1]={-1,-1};
    }
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;
        while(k--){
            int x;
            cin>>x;
            tcv[x].push_back(i);
            vct[i].push_back(x);
        }
    }
    int in;
    cin>>in;
    deque<pair<int,int>>dq;
    for(int i=1;i<=n;i++){
        if(vct[i].empty())dq.push_back({i,0});
    }
    if(dq.empty()){
        cout<<"Draw";
        return 0;
    }
    bool bl=0;
    while(dq.size()){
        int a=dq.front().first,b=dq.front().second;
        dq.pop_front();
        for(auto &i:tcv[a]){
            if(vis[i][b^1].first==-1){
                vis[i][b^1]={a,b};
                dq.push_back({i,b^1});
            }
        }
    }
    if(vis[in][1].first==-1){
        if(dfs1(in))cout<<"Draw";
        else cout<<"Lose";
        return 0;
    }
    cout<<"Win\n";
    int a=in,b=1;
    while(vis[a][b].first!=-1){
        cout<<a<<' ';
        int A=a,B=b;
        a=vis[A][B].first;
        b=vis[A][B].second;
    }
    cout<<a;
}

Compilation message (stderr)

D.cpp: In function 'int main()':
D.cpp:53:10: warning: unused variable 'bl' [-Wunused-variable]
   53 |     bool bl=0;
      |          ^~

• Subtask 1: 17 / 17
• Subtask 2: 19 / 19
• Subtask 3: 15 / 15
• Subtask 4: 11 / 11
• Subtask 5: 38 / 38