oj.uz

Submission #415673

# Submission time Handle Problem Language Result Execution time Memory
415673 2021-06-01T11:01:42 Z SeDunion Toy Train (IOI17_train) C++17
34 / 100
 603 ms 10828 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, const vector<int>&answer) {
	for (int i = 0 ; i < n ; ++ i) {
		if (answer[i] != -1) {
			deg[i] = -2409;
			continue;
		}
		deg[i] = 0;
		for (int j : g[i]) {
			deg[i] += answer[j] == -1;
		}
	}
	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, answer);
		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, answer);
		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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 10316 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 10704 KB Output is correct
2 Correct 301 ms 10708 KB Output is correct
3 Correct 457 ms 10716 KB Output is correct
4 Correct 17 ms 10660 KB Output is correct
5 Correct 22 ms 10596 KB Output is correct
6 Correct 17 ms 10776 KB Output is correct
7 Correct 15 ms 10772 KB Output is correct
8 Correct 16 ms 10736 KB Output is correct
9 Correct 17 ms 10828 KB Output is correct
10 Correct 15 ms 10716 KB Output is correct
11 Correct 18 ms 10788 KB Output is correct
12 Correct 16 ms 10700 KB Output is correct
13 Correct 15 ms 10716 KB Output is correct
14 Correct 15 ms 10740 KB Output is correct
15 Correct 15 ms 10700 KB Output is correct
16 Correct 15 ms 10772 KB Output is correct
17 Correct 15 ms 10700 KB Output is correct
18 Correct 603 ms 10528 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10444 KB Output is correct
2 Correct 15 ms 10532 KB Output is correct
3 Correct 15 ms 10524 KB Output is correct
4 Correct 17 ms 10652 KB Output is correct
5 Correct 17 ms 10572 KB Output is correct
6 Correct 17 ms 10572 KB Output is correct
7 Correct 17 ms 10616 KB Output is correct
8 Correct 14 ms 10572 KB Output is correct
9 Correct 14 ms 10588 KB Output is correct
10 Correct 15 ms 10572 KB Output is correct
11 Correct 17 ms 10572 KB Output is correct
12 Correct 15 ms 10528 KB Output is correct
13 Correct 16 ms 10652 KB Output is correct
14 Correct 14 ms 10444 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10572 KB Output is correct
2 Correct 15 ms 10556 KB Output is correct
3 Correct 18 ms 10528 KB Output is correct
4 Correct 15 ms 10460 KB Output is correct
5 Correct 8 ms 9676 KB Output is correct
6 Correct 12 ms 10188 KB Output is correct
7 Correct 13 ms 10216 KB Output is correct
8 Correct 12 ms 10316 KB Output is correct
9 Correct 13 ms 10188 KB Output is correct
10 Correct 8 ms 9804 KB Output is correct
11 Correct 13 ms 10188 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 10316 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -