oj.uz

Submission #282853

# Submission time Handle Problem Language Result Execution time Memory
282853 2020-08-25T04:47:42 Z 최은수(#5745) Sleepy game (innopolis2018_final_D) C++17
100 / 100
 107 ms 25336 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
vector<int>adj[400010];
int pa[400010];
int chk[400010];
bool cyc;
void dfs(int x)
{
    chk[x]=1;
    for(int&t:adj[x])
    {
        if(chk[t]==0)
            pa[t]=x,dfs(t);
        else if(chk[t]==1)
            cyc=1;
    }
    chk[x]=2;
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=0;i++<n;)
    {
        int c;
        cin>>c;
        for(int j=0;j<c;j++)
        {
            int v;
            cin>>v;
            adj[i].eb(v+n);
            adj[i+n].eb(v);
        }
    }
    int s;
    cin>>s;
    dfs(s);
    int wv=-1;
    for(int i=n;i++<n*2;)
        if(chk[i]==2&&adj[i].empty())
            wv=i;
    if(wv!=-1)
    {
        cout<<"Win"<<endl;
        vector<int>path;
        int x=wv;
        while(x!=s)
            path.eb(x>n?x-n:x),x=pa[x];
        reverse(all(path));
        cout<<s;
        for(int&t:path)
            cout<<' '<<t;
        cout<<endl;
    }
    else if(cyc)
        cout<<"Draw"<<endl;
    else
        cout<<"Lose"<<endl;
    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Correct solution.
2 Correct 7 ms 9728 KB Correct solution.
3 Correct 7 ms 9728 KB Correct solution.
4 Correct 61 ms 20728 KB Correct solution.
5 Correct 32 ms 16384 KB Correct solution.
6 Correct 43 ms 18936 KB Correct solution.
7 Correct 77 ms 24176 KB Correct solution.
8 Correct 72 ms 25336 KB Correct solution.
9 Correct 61 ms 23032 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9856 KB Correct solution.
2 Correct 7 ms 9728 KB Correct solution.
3 Correct 7 ms 9728 KB Correct solution.
4 Correct 55 ms 16376 KB Correct solution.
5 Correct 7 ms 9856 KB Correct solution.
6 Correct 13 ms 11008 KB Correct solution.
7 Correct 90 ms 22008 KB Correct solution.
8 Correct 78 ms 22044 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Correct solution.
2 Correct 7 ms 9728 KB Correct solution.
3 Correct 7 ms 9728 KB Correct solution.
4 Correct 7 ms 9728 KB Correct solution.
5 Correct 7 ms 9728 KB Correct solution.
6 Correct 8 ms 9856 KB Correct solution.
7 Correct 7 ms 9856 KB Correct solution.
8 Correct 7 ms 9856 KB Correct solution.
9 Correct 7 ms 9856 KB Correct solution.
10 Correct 7 ms 9856 KB Correct solution.
11 Correct 7 ms 9856 KB Correct solution.

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Correct solution.
2 Correct 7 ms 9728 KB Correct solution.
3 Correct 7 ms 9728 KB Correct solution.
4 Correct 7 ms 9728 KB Correct solution.
5 Correct 7 ms 9728 KB Correct solution.
6 Correct 8 ms 9856 KB Correct solution.
7 Correct 7 ms 9856 KB Correct solution.
8 Correct 7 ms 9856 KB Correct solution.
9 Correct 7 ms 9856 KB Correct solution.
10 Correct 7 ms 9856 KB Correct solution.
11 Correct 7 ms 9856 KB Correct solution.
12 Correct 32 ms 12920 KB Correct solution.
13 Correct 36 ms 13688 KB Correct solution.
14 Correct 33 ms 13176 KB Correct solution.
15 Correct 35 ms 13184 KB Correct solution.
16 Correct 34 ms 13176 KB Correct solution.
17 Correct 10 ms 10496 KB Correct solution.
18 Correct 31 ms 13560 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Correct solution.
2 Correct 7 ms 9728 KB Correct solution.
3 Correct 7 ms 9728 KB Correct solution.
4 Correct 61 ms 20728 KB Correct solution.
5 Correct 32 ms 16384 KB Correct solution.
6 Correct 43 ms 18936 KB Correct solution.
7 Correct 77 ms 24176 KB Correct solution.
8 Correct 72 ms 25336 KB Correct solution.
9 Correct 61 ms 23032 KB Correct solution.
10 Correct 7 ms 9856 KB Correct solution.
11 Correct 7 ms 9728 KB Correct solution.
12 Correct 7 ms 9728 KB Correct solution.
13 Correct 55 ms 16376 KB Correct solution.
14 Correct 7 ms 9856 KB Correct solution.
15 Correct 13 ms 11008 KB Correct solution.
16 Correct 90 ms 22008 KB Correct solution.
17 Correct 78 ms 22044 KB Correct solution.
18 Correct 7 ms 9728 KB Correct solution.
19 Correct 7 ms 9728 KB Correct solution.
20 Correct 7 ms 9728 KB Correct solution.
21 Correct 7 ms 9728 KB Correct solution.
22 Correct 7 ms 9728 KB Correct solution.
23 Correct 8 ms 9856 KB Correct solution.
24 Correct 7 ms 9856 KB Correct solution.
25 Correct 7 ms 9856 KB Correct solution.
26 Correct 7 ms 9856 KB Correct solution.
27 Correct 7 ms 9856 KB Correct solution.
28 Correct 7 ms 9856 KB Correct solution.
29 Correct 32 ms 12920 KB Correct solution.
30 Correct 36 ms 13688 KB Correct solution.
31 Correct 33 ms 13176 KB Correct solution.
32 Correct 35 ms 13184 KB Correct solution.
33 Correct 34 ms 13176 KB Correct solution.
34 Correct 10 ms 10496 KB Correct solution.
35 Correct 31 ms 13560 KB Correct solution.
36 Correct 82 ms 19320 KB Correct solution.
37 Correct 96 ms 21264 KB Correct solution.
38 Correct 87 ms 22008 KB Correct solution.
39 Correct 107 ms 19192 KB Correct solution.
40 Correct 89 ms 19220 KB Correct solution.
41 Correct 62 ms 23032 KB Correct solution.
42 Correct 69 ms 21496 KB Correct solution.