Submission #1178328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178328		pedroslrey	Toy Train (IOI17_train)	C++20	100 / 100	294 ms	1524 KiB

train

#include <bits/stdc++.h>
#include "train.h"

using namespace std;
using graph = vector<vector<int>>;

vector<int> who_wins(vector<int> own, vector<int> rs, vector<int> us, vector<int> vs) {
	int n = own.size();

	graph G(n), G1(n);
	for (int i = 0; i < us.size(); ++i) {
		G[us[i]].push_back(vs[i]);
		G1[vs[i]].push_back(us[i]);
	}

	auto reach = [&](vector<bool> &ss) {
		vector<bool> marc = ss;
		
		queue<int> q;
		for (int i = 0; i < n; ++i)
			if (marc[i]) q.push(i);

		vector<int> in(n);
		for (int i = 0; i < n; ++i)
			if (!own[i]) in[i] = G[i].size();

		while (!q.empty()) {
			int u = q.front(); q.pop();

			for (int v: G1[u]) if (!marc[v]) 
				if (own[v]) { marc[v] = true; q.push(v); }
				else { --in[v]; if (in[v] == 0) { marc[v] = true; q.push(v); }}
		}

		return marc;
	};

	vector<bool> rline(rs.begin(), rs.end());

	while (true) {
		vector<bool> fs = reach(rline);

		bool change = false;
		for (int u = 0; u < n; ++u) if (rline[u])
			if (own[u]) {
				bool ok = false;
				for (int v: G[u])
					if (fs[v]) ok = true;
				if (!ok) { rline[u] = false; change = true; }
			}
			else {
				bool ok = true;
				for (int v: G[u])
					if (!fs[v]) ok = false;

				if (!ok) { rline[u] = false; change = true; }
			}

		if (!change) break;
	}

	auto ans = reach(rline);

	return vector<int>(ans.begin(), ans.end());
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51