oj.uz

Submission #766729

# Submission time Handle Problem Language Result Execution time Memory
766729 2023-06-26T05:38:36 Z SanguineChameleon Toy Train (IOI17_train) C++17
22 / 100
 753 ms 1424 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> 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();
	for (int i = 0; i < m; i++) {
		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_sub3) {
		return sub3();
	}
	if (is_sub4) {
		return sub4();
	}
	return vector<int>();
}

Subtask #1
0 / 5.0

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

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 115 ms 1284 KB Output is correct
2 Correct 118 ms 1252 KB Output is correct
3 Correct 123 ms 1224 KB Output is correct
4 Correct 82 ms 1128 KB Output is correct
5 Correct 96 ms 1108 KB Output is correct
6 Correct 458 ms 1080 KB Output is correct
7 Correct 138 ms 1036 KB Output is correct
8 Correct 78 ms 1056 KB Output is correct
9 Correct 160 ms 1064 KB Output is correct
10 Correct 66 ms 980 KB Output is correct
11 Correct 107 ms 1008 KB Output is correct
12 Correct 18 ms 980 KB Output is correct
13 Correct 348 ms 1200 KB Output is correct
14 Correct 653 ms 1220 KB Output is correct
15 Correct 513 ms 1228 KB Output is correct
16 Correct 14 ms 980 KB Output is correct
17 Correct 54 ms 1148 KB Output is correct
18 Correct 244 ms 972 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 1044 KB Output is correct
2 Correct 106 ms 1156 KB Output is correct
3 Correct 109 ms 1236 KB Output is correct
4 Correct 18 ms 1244 KB Output is correct
5 Correct 288 ms 1248 KB Output is correct
6 Correct 321 ms 1236 KB Output is correct
7 Correct 312 ms 1348 KB Output is correct
8 Correct 74 ms 1108 KB Output is correct
9 Correct 13 ms 1108 KB Output is correct
10 Correct 726 ms 1424 KB Output is correct
11 Correct 753 ms 1364 KB Output is correct
12 Correct 740 ms 1328 KB Output is correct
13 Correct 229 ms 1236 KB Output is correct
14 Correct 173 ms 1204 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 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 Incorrect 2 ms 724 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -