oj.uz

Submission #766731

# Submission time Handle Problem Language Result Execution time Memory
766731 2023-06-26T05:43:55 Z SanguineChameleon Toy Train (IOI17_train) C++17
27 / 100
 719 ms 1328 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e3 + 20;
vector<int> adj[maxn];
bool charge[maxn];
bool good[maxn];
bool flag[maxn];
int own[maxn];
int n, m;
int root;

bool dfs1(int u) {
	flag[u] = true;
	for (auto v: adj[u]) {
		if (v == root) {
			return true;
		}
		else if (!flag[v] && dfs1(v)) {
			return true;
		}
	}
	return false;
}

bool dfs2(int u) {
	flag[u] = true;
	if (good[u]) {
		return true;
	}
	for (auto v: adj[u]) {
		if (!flag[v] && dfs2(v)) {
			return true;
		}
	}
	return false;
}

bool dfs3(int u) {
	flag[u] = true;
	for (auto v: adj[u]) {
		if (charge[v]) {
			continue;
		}
		if (v == root) {
			return true;
		}
		else if (!flag[v] && dfs3(v)) {
			return true;
		}
	}
	return false;
}

vector<int> sub3() {
	for (root = 0; root < n; root++) {
		if (!charge[root]) {
			continue;
		}
		for (int u = 0; u < n; u++) {
			flag[u] = false;
		}
		good[root] = dfs1(root);
	}
	vector<int> res(n);
	for (root = 0; root < n; root++) {
		for (int u = 0; u < n; u++) {
			flag[u] = false;
		}
		res[root] = dfs2(root);
	}
	return res;
}

vector<int> sub4() {
	for (root = 0; root < n; root++) {
		if (charge[root]) {
			continue;
		}
		for (int u = 0; u < n; u++) {
			flag[u] = false;
		}
		good[root] = dfs3(root);
	}
	vector<int> res(n);
	for (root = 0; root < n; root++) {
		for (int u = 0; u < n; u++) {
			flag[u] = false;
		}
		res[root] = dfs2(root) ^ 1;
	}
	return res;
}

vector<int> sub1() {
	vector<int> res(n);
	for (int i = n - 1; i >= 0; i--) {
		if (own[i] == 1) {
			res[i] = 0;
			for (auto j: adj[i]) {
				if (j == i) {
					if (charge[i]) {
						res[i] = 1;
						break;
					}
				}
				else if (res[j] == 1) {
					res[i] = 1;
					break;
				}
			}
		}
		else {
			res[i] = 1;
			for (auto j: adj[i]) {
				if (j == i) {
					if (!charge[i]) {
						res[i] = 0;
						break;
					}
				}
				else if (res[j] == 0) {
					res[i] = 0;
					break;
				}
			}
		}
	}
	return res;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = a.size();
	for (int i = 0; i < n; i++) {
		own[i] = a[i];
		charge[i] = r[i];
	}
	m = u.size();
	bool is_sub1 = true;
	for (int i = 0; i < m; i++) {
		is_sub1 &= (v[i] == u[i]) || (v[i] == u[i] + 1);
		adj[u[i]].push_back(v[i]);
	}
	bool is_sub3 = true;
	bool is_sub4 = true;
	for (int i = 0; i < n; i++) {
		is_sub3 &= (own[i] == 1);
		is_sub4 &= (own[i] == 0);
	}
	if (is_sub1) {
		return sub1();
	}
	if (is_sub3) {
		return sub3();
	}
	if (is_sub4) {
		return sub4();
	}
	return vector<int>();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 848 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 3 ms 772 KB Output is correct
11 Correct 3 ms 724 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 1292 KB Output is correct
2 Correct 117 ms 1276 KB Output is correct
3 Correct 119 ms 1152 KB Output is correct
4 Correct 82 ms 1132 KB Output is correct
5 Correct 96 ms 1116 KB Output is correct
6 Correct 417 ms 980 KB Output is correct
7 Correct 139 ms 1028 KB Output is correct
8 Correct 77 ms 980 KB Output is correct
9 Correct 162 ms 1060 KB Output is correct
10 Correct 72 ms 1024 KB Output is correct
11 Correct 103 ms 1008 KB Output is correct
12 Correct 18 ms 980 KB Output is correct
13 Correct 340 ms 1212 KB Output is correct
14 Correct 678 ms 1208 KB Output is correct
15 Correct 482 ms 1204 KB Output is correct
16 Correct 15 ms 980 KB Output is correct
17 Correct 55 ms 1108 KB Output is correct
18 Correct 240 ms 1076 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 1036 KB Output is correct
2 Correct 105 ms 980 KB Output is correct
3 Correct 108 ms 980 KB Output is correct
4 Correct 18 ms 1048 KB Output is correct
5 Correct 289 ms 1056 KB Output is correct
6 Correct 316 ms 1056 KB Output is correct
7 Correct 323 ms 1100 KB Output is correct
8 Correct 73 ms 1004 KB Output is correct
9 Correct 13 ms 984 KB Output is correct
10 Correct 719 ms 1228 KB Output is correct
11 Correct 707 ms 1328 KB Output is correct
12 Correct 713 ms 1208 KB Output is correct
13 Correct 229 ms 1112 KB Output is correct
14 Correct 168 ms 1008 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 980 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 848 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 3 ms 772 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Incorrect 1 ms 340 KB WA in grader: Wrong returned array size
13 Halted 0 ms 0 KB -