Submission #766727

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
766727	2023-06-26T05:34:40 Z	SanguineChameleon	Toy Train (IOI17_train)	C++17	11 / 100	668 ms	1488 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;
}

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() {
	return vector<int>();
}

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	852 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	113 ms	1488 KB	Output is correct
2	Correct	110 ms	1392 KB	Output is correct
3	Correct	121 ms	1364 KB	Output is correct
4	Correct	98 ms	1460 KB	Output is correct
5	Correct	96 ms	1320 KB	Output is correct
6	Correct	408 ms	1284 KB	Output is correct
7	Correct	143 ms	1236 KB	Output is correct
8	Correct	78 ms	1236 KB	Output is correct
9	Correct	159 ms	1252 KB	Output is correct
10	Correct	68 ms	1236 KB	Output is correct
11	Correct	103 ms	1108 KB	Output is correct
12	Correct	18 ms	1076 KB	Output is correct
13	Correct	361 ms	1408 KB	Output is correct
14	Correct	668 ms	1408 KB	Output is correct
15	Correct	471 ms	1412 KB	Output is correct
16	Correct	15 ms	1236 KB	Output is correct
17	Correct	54 ms	1364 KB	Output is correct
18	Correct	242 ms	1132 KB	Output is correct