Submission #766731

#	Time	Username	Problem	Language	Result	Execution time	Memory
766731		SanguineChameleon	Toy Train (IOI17_train)	C++17	27 / 100	719 ms	1328 KiB

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] && 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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51