oj.uz

Submission #583900

# Submission time Handle Problem Language Result Execution time Memory
583900 2022-06-26T12:54:27 Z MrDeboo Sleepy game (innopolis2018_final_D) C++17
100 / 100
 134 ms 20536 KB 
#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

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Correct solution.
2 Correct 4 ms 8148 KB Correct solution.
3 Correct 4 ms 8276 KB Correct solution.
4 Correct 49 ms 17316 KB Correct solution.
5 Correct 32 ms 14540 KB Correct solution.
6 Correct 52 ms 16716 KB Correct solution.
7 Correct 90 ms 15672 KB Correct solution.
8 Correct 39 ms 15168 KB Correct solution.
9 Correct 44 ms 15120 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Correct solution.
2 Correct 4 ms 8148 KB Correct solution.
3 Correct 4 ms 8148 KB Correct solution.
4 Correct 90 ms 15480 KB Correct solution.
5 Correct 4 ms 8148 KB Correct solution.
6 Correct 10 ms 8916 KB Correct solution.
7 Correct 85 ms 15936 KB Correct solution.
8 Correct 57 ms 16224 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Correct solution.
2 Correct 4 ms 8148 KB Correct solution.
3 Correct 4 ms 8096 KB Correct solution.
4 Correct 4 ms 8148 KB Correct solution.
5 Correct 4 ms 8168 KB Correct solution.
6 Correct 5 ms 8148 KB Correct solution.
7 Correct 7 ms 8228 KB Correct solution.
8 Correct 5 ms 8148 KB Correct solution.
9 Correct 8 ms 8148 KB Correct solution.
10 Correct 4 ms 8148 KB Correct solution.
11 Correct 5 ms 8276 KB Correct solution.

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Correct solution.
2 Correct 4 ms 8148 KB Correct solution.
3 Correct 4 ms 8096 KB Correct solution.
4 Correct 4 ms 8148 KB Correct solution.
5 Correct 4 ms 8168 KB Correct solution.
6 Correct 5 ms 8148 KB Correct solution.
7 Correct 7 ms 8228 KB Correct solution.
8 Correct 5 ms 8148 KB Correct solution.
9 Correct 8 ms 8148 KB Correct solution.
10 Correct 4 ms 8148 KB Correct solution.
11 Correct 5 ms 8276 KB Correct solution.
12 Correct 28 ms 12976 KB Correct solution.
13 Correct 31 ms 14412 KB Correct solution.
14 Correct 29 ms 13772 KB Correct solution.
15 Correct 33 ms 14076 KB Correct solution.
16 Correct 31 ms 14048 KB Correct solution.
17 Correct 7 ms 8404 KB Correct solution.
18 Correct 31 ms 14784 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Correct solution.
2 Correct 4 ms 8148 KB Correct solution.
3 Correct 4 ms 8276 KB Correct solution.
4 Correct 49 ms 17316 KB Correct solution.
5 Correct 32 ms 14540 KB Correct solution.
6 Correct 52 ms 16716 KB Correct solution.
7 Correct 90 ms 15672 KB Correct solution.
8 Correct 39 ms 15168 KB Correct solution.
9 Correct 44 ms 15120 KB Correct solution.
10 Correct 4 ms 8148 KB Correct solution.
11 Correct 4 ms 8148 KB Correct solution.
12 Correct 4 ms 8148 KB Correct solution.
13 Correct 90 ms 15480 KB Correct solution.
14 Correct 4 ms 8148 KB Correct solution.
15 Correct 10 ms 8916 KB Correct solution.
16 Correct 85 ms 15936 KB Correct solution.
17 Correct 57 ms 16224 KB Correct solution.
18 Correct 4 ms 8020 KB Correct solution.
19 Correct 4 ms 8148 KB Correct solution.
20 Correct 4 ms 8096 KB Correct solution.
21 Correct 4 ms 8148 KB Correct solution.
22 Correct 4 ms 8168 KB Correct solution.
23 Correct 5 ms 8148 KB Correct solution.
24 Correct 7 ms 8228 KB Correct solution.
25 Correct 5 ms 8148 KB Correct solution.
26 Correct 8 ms 8148 KB Correct solution.
27 Correct 4 ms 8148 KB Correct solution.
28 Correct 5 ms 8276 KB Correct solution.
29 Correct 28 ms 12976 KB Correct solution.
30 Correct 31 ms 14412 KB Correct solution.
31 Correct 29 ms 13772 KB Correct solution.
32 Correct 33 ms 14076 KB Correct solution.
33 Correct 31 ms 14048 KB Correct solution.
34 Correct 7 ms 8404 KB Correct solution.
35 Correct 31 ms 14784 KB Correct solution.
36 Correct 76 ms 15716 KB Correct solution.
37 Correct 92 ms 16968 KB Correct solution.
38 Correct 134 ms 17296 KB Correct solution.
39 Correct 92 ms 16976 KB Correct solution.
40 Correct 100 ms 17140 KB Correct solution.
41 Correct 43 ms 15124 KB Correct solution.
42 Correct 116 ms 20536 KB Correct solution.