oj.uz

Submission #282881

# Submission time Handle Problem Language Result Execution time Memory
282881 2020-08-25T06:21:09 Z 임성재(#5752) Sleepy game (innopolis2018_final_D) C++17
100 / 100
 100 ms 8052 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
int in[100010];
vector<int> g[100010];
queue<int> q;
int p[200010];
bool chk[200010];
bool cy[100010];

int main() {
	fast;

	cin >> n >> m;

	for(int i=1; i<=n; i++) {
		int out;
		cin >> out;

		for(int j=0; j<out; j++) {
			int v;
			cin >> v;

			g[v].eb(i);
			in[i]++;
		}

		if(out == 0) {
			chk[i] = true;
			q.em(i);
		}
	}

	while(q.size()) {
		int x = q.front();
		q.pop();

		int st = 0;

		if(x > n) {
			x -= n;
			st = 1;
		}

		for(auto i : g[x]) {
			if(chk[i + (1 - st) * n]) continue;
			
			p[i + (1 - st) * n] = x + st * n;
			chk[i + (1 - st) * n] = true;
			q.em(i + (1 - st) * n);
		}
	}

	for(int i=1; i<=n; i++) {
		cy[i] = true;
		if(in[i] == 0) q.em(i);
	}

	while(q.size()) {
		int x = q.front();
		q.pop();

		cy[x] = false;

		for(auto i : g[x]) {
			in[i]--;
			if(in[i] == 0) {
				q.em(i);
			}
		}
	}

	int s;
	cin >> s;

	if(chk[s + n]) {
		cout << "Win\n";

		for(int i = s + n; i; i = p[i]) {
			cout << (i-1) % n + 1 << " ";
		}
	}
	else if(cy[s]) {
		cout << "Draw\n";
	}
	else {
		cout << "Lose\n";
	}
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 2 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 28 ms 6256 KB Correct solution.
5 Correct 25 ms 4992 KB Correct solution.
6 Correct 44 ms 6136 KB Correct solution.
7 Correct 62 ms 7928 KB Correct solution.
8 Correct 43 ms 6264 KB Correct solution.
9 Correct 34 ms 6400 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 2 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 88 ms 6904 KB Correct solution.
5 Correct 2 ms 2688 KB Correct solution.
6 Correct 8 ms 3200 KB Correct solution.
7 Correct 100 ms 7672 KB Correct solution.
8 Correct 60 ms 8052 KB Correct solution.

Subtask #3
15.0 / 15.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 2 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 2 ms 2688 KB Correct solution.
5 Correct 2 ms 2688 KB Correct solution.
6 Correct 2 ms 2688 KB Correct solution.
7 Correct 2 ms 2688 KB Correct solution.
8 Correct 3 ms 2688 KB Correct solution.
9 Correct 2 ms 2688 KB Correct solution.
10 Correct 2 ms 2688 KB Correct solution.
11 Correct 3 ms 2688 KB Correct solution.
12 Correct 22 ms 3840 KB Correct solution.
13 Correct 26 ms 4096 KB Correct solution.
14 Correct 27 ms 4216 KB Correct solution.
15 Correct 27 ms 4216 KB Correct solution.
16 Correct 26 ms 4216 KB Correct solution.
17 Correct 3 ms 2816 KB Correct solution.
18 Correct 27 ms 4216 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 2 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 28 ms 6256 KB Correct solution.
5 Correct 25 ms 4992 KB Correct solution.
6 Correct 44 ms 6136 KB Correct solution.
7 Correct 62 ms 7928 KB Correct solution.
8 Correct 43 ms 6264 KB Correct solution.
9 Correct 34 ms 6400 KB Correct solution.
10 Correct 2 ms 2688 KB Correct solution.
11 Correct 2 ms 2688 KB Correct solution.
12 Correct 2 ms 2688 KB Correct solution.
13 Correct 88 ms 6904 KB Correct solution.
14 Correct 2 ms 2688 KB Correct solution.
15 Correct 8 ms 3200 KB Correct solution.
16 Correct 100 ms 7672 KB Correct solution.
17 Correct 60 ms 8052 KB Correct solution.
18 Correct 2 ms 2688 KB Correct solution.
19 Correct 2 ms 2688 KB Correct solution.
20 Correct 2 ms 2688 KB Correct solution.
21 Correct 2 ms 2688 KB Correct solution.
22 Correct 2 ms 2688 KB Correct solution.
23 Correct 2 ms 2688 KB Correct solution.
24 Correct 2 ms 2688 KB Correct solution.
25 Correct 3 ms 2688 KB Correct solution.
26 Correct 2 ms 2688 KB Correct solution.
27 Correct 2 ms 2688 KB Correct solution.
28 Correct 3 ms 2688 KB Correct solution.
29 Correct 22 ms 3840 KB Correct solution.
30 Correct 26 ms 4096 KB Correct solution.
31 Correct 27 ms 4216 KB Correct solution.
32 Correct 27 ms 4216 KB Correct solution.
33 Correct 26 ms 4216 KB Correct solution.
34 Correct 3 ms 2816 KB Correct solution.
35 Correct 27 ms 4216 KB Correct solution.
36 Correct 57 ms 6408 KB Correct solution.
37 Correct 71 ms 7160 KB Correct solution.
38 Correct 99 ms 7672 KB Correct solution.
39 Correct 81 ms 7416 KB Correct solution.
40 Correct 68 ms 7416 KB Correct solution.
41 Correct 32 ms 6272 KB Correct solution.
42 Correct 83 ms 7404 KB Correct solution.