oj.uz

Submission #415667

# Submission time Handle Problem Language Result Execution time Memory
415667 2021-06-01T10:53:21 Z SeDunion Toy Train (IOI17_train) C++17
28 / 100
 293 ms 11160 KB 
#include "train.h"
#include<bits/stdc++.h>
using namespace std;

const int A = 1;
const int B = 0;

vector<int>g[(int)2e5+22], rg[(int)2e5+22];

int n, m;

int deg[(int)2e5+22];

queue<int>q;

vector<int>f(const int type, const vector<int>&S, const vector<int>&a) {
	for (int i = 0 ; i < n ; ++ i) {
		deg[i] = g[i].size();
	}
	for (int i : S) {
		deg[i] = -1;
		q.push(i);
	}
	while (q.size()) {
		int v = q.front(); q.pop();
		for (int from : rg[v]) if (deg[from] != -1) {
			if (a[from] == type) {
				deg[from] = -1;
				q.push(from);
			} else {
				if (--deg[from] == 0) {
					deg[from] = -1;
					q.push(from);
				}
			}
		}
	}
	vector<int>ans;
	for (int i = 0 ; i < n ; ++ i) {
		if (deg[i] == -1) {
			ans.emplace_back(i);
		}
	}
	return ans;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = a.size();
	m = u.size();
	for (int i = 0 ; i < m ; ++ i) {
		g[u[i]].emplace_back(v[i]);
		rg[v[i]].emplace_back(u[i]);
	}
	vector<int>answer(n, -1);
	vector<int>R;
	vector<int>fa;
	vector<int>nfa;
	vector<int>infa;
	vector<int>fb;
	while (true) {
		R.clear();
		for (int i = 0 ; i < n ; ++ i) {
			if (r[i] && answer[i] == -1) {
				R.emplace_back(i);
			}
		}
		if (R.empty()) {
			for (int i = 0 ; i < n ; ++ i) {
				if (answer[i] == -1) {
					answer[i] = 0;
				}
			}
			break;
		}
		fa = f(A, R, a);
		infa.assign(n, 0);
		for (int i : fa) infa[i] = 1;
		nfa.clear();
		for (int i = 0 ; i < n ; ++ i) {
			if (answer[i] == -1 && infa[i] == 0) {
				nfa.emplace_back(i);
			}
		}
		fb = f(B, nfa, a);
		if (fb.empty()) {
			for (int i = 0 ; i < n ; ++ i) {
				if (answer[i] == -1) {
					answer[i] = 1;
				}
			}
			break;
		}
		for (int i : fb) answer[i] = 0;
	}
	return answer;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10316 KB Output is correct
2 Correct 14 ms 10444 KB Output is correct
3 Correct 13 ms 10316 KB Output is correct
4 Correct 12 ms 10316 KB Output is correct
5 Correct 12 ms 10344 KB Output is correct
6 Correct 11 ms 10344 KB Output is correct
7 Correct 12 ms 10316 KB Output is correct
8 Correct 12 ms 10444 KB Output is correct
9 Correct 11 ms 10376 KB Output is correct
10 Correct 11 ms 10344 KB Output is correct
11 Correct 11 ms 10344 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 6 ms 9692 KB Output is correct
4 Correct 6 ms 9592 KB Output is correct
5 Correct 9 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Incorrect 7 ms 9700 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 10908 KB Output is correct
2 Correct 201 ms 10828 KB Output is correct
3 Correct 293 ms 11160 KB Output is correct
4 Correct 16 ms 10828 KB Output is correct
5 Incorrect 16 ms 10860 KB 3rd lines differ - on the 11th token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10652 KB Output is correct
2 Correct 18 ms 10672 KB Output is correct
3 Correct 16 ms 10772 KB Output is correct
4 Correct 15 ms 10828 KB Output is correct
5 Correct 18 ms 10832 KB Output is correct
6 Correct 17 ms 10828 KB Output is correct
7 Correct 16 ms 10816 KB Output is correct
8 Correct 16 ms 10700 KB Output is correct
9 Correct 15 ms 10700 KB Output is correct
10 Correct 15 ms 10728 KB Output is correct
11 Correct 16 ms 10820 KB Output is correct
12 Correct 16 ms 10824 KB Output is correct
13 Correct 15 ms 10860 KB Output is correct
14 Correct 16 ms 10700 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10732 KB Output is correct
2 Correct 14 ms 10700 KB Output is correct
3 Correct 16 ms 10820 KB Output is correct
4 Correct 15 ms 10620 KB Output is correct
5 Correct 8 ms 9676 KB Output is correct
6 Correct 11 ms 10348 KB Output is correct
7 Correct 12 ms 10336 KB Output is correct
8 Correct 14 ms 10436 KB Output is correct
9 Correct 11 ms 10444 KB Output is correct
10 Correct 8 ms 9804 KB Output is correct
11 Correct 12 ms 10344 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10316 KB Output is correct
2 Correct 14 ms 10444 KB Output is correct
3 Correct 13 ms 10316 KB Output is correct
4 Correct 12 ms 10316 KB Output is correct
5 Correct 12 ms 10344 KB Output is correct
6 Correct 11 ms 10344 KB Output is correct
7 Correct 12 ms 10316 KB Output is correct
8 Correct 12 ms 10444 KB Output is correct
9 Correct 11 ms 10376 KB Output is correct
10 Correct 11 ms 10344 KB Output is correct
11 Correct 11 ms 10344 KB Output is correct
12 Correct 7 ms 9676 KB Output is correct
13 Correct 7 ms 9676 KB Output is correct
14 Correct 6 ms 9692 KB Output is correct
15 Correct 6 ms 9592 KB Output is correct
16 Correct 9 ms 9676 KB Output is correct
17 Correct 6 ms 9676 KB Output is correct
18 Correct 6 ms 9676 KB Output is correct
19 Incorrect 7 ms 9700 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
20 Halted 0 ms 0 KB -