Submission #583896

#	Time	Username	Problem	Language	Result	Execution time	Memory
583896		MrDeboo	Sleepy game (innopolis2018_final_D)	C++17	19 / 100	115 ms	17380 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];
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;
    }
    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){
        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;
}

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