Submission #1215315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215315		ColourAttila	Toy Train (IOI17_train)	C++20	0 / 100	2096 ms	1088 KiB

train

#include <bits/stdc++.h>

using namespace std;

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

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

    //marc[i] = 1 if starting from vertex i it i spossible to reach any vertex in ss regardless of the opponents moves
	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: G[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;
	};

    //current set of verticies to check
	vector<bool> rline(rs.begin(), rs.end());
    bool change = true;

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

		change = false;
		for (int u = 0; u < n; ++u)  {
            if (!rline[u]) continue;
			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; 
                }
			}
        }
	}

	auto ans = reach(rline);

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

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