Submission #766728

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
766728	2023-06-26T05:36:58 Z	SanguineChameleon	Toy Train (IOI17_train)	C++17	11 / 100	643 ms	1248 KB

train

#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] && dfs1(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	110 ms	1236 KB	Output is correct
2	Correct	111 ms	1248 KB	Output is correct
3	Correct	149 ms	1148 KB	Output is correct
4	Correct	83 ms	1120 KB	Output is correct
5	Correct	98 ms	1108 KB	Output is correct
6	Correct	409 ms	1056 KB	Output is correct
7	Correct	144 ms	980 KB	Output is correct
8	Correct	76 ms	1064 KB	Output is correct
9	Correct	156 ms	1064 KB	Output is correct
10	Correct	68 ms	1020 KB	Output is correct
11	Correct	114 ms	1004 KB	Output is correct
12	Correct	18 ms	980 KB	Output is correct
13	Correct	382 ms	1200 KB	Output is correct
14	Correct	643 ms	1108 KB	Output is correct
15	Correct	481 ms	1212 KB	Output is correct
16	Correct	15 ms	980 KB	Output is correct
17	Correct	56 ms	1152 KB	Output is correct
18	Correct	257 ms	1012 KB	Output is correct