Submission #1215522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215522		ColourAttila	Toy Train (IOI17_train)	C++20	11 / 100	141 ms	1528 KiB

train

#include <bits/stdc++.h>
//#include "train.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), G_rev(n);
	for (int i = 0; i < us.size(); ++i) {
		G[us[i]].push_back(vs[i]);
		G_rev[vs[i]].push_back(us[i]);
	}

    //volt[i] = 1 if starting from vertex i it is possible to reach any vertex in ss regardless of the opponents moves
	auto reach = [&](vector<bool> &ss) {
		vector<bool> volt = ss;
		
		queue<int> q;
		for (int i = 0; i < n; ++i) {
			if (volt[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_rev[u]) {
                if (volt[v]) continue;
				if (own[v]) { 
                    volt[v] = true; 
                    q.push(v);
                }
				else { 
                    if (in[v]-- == 0) { 
                        volt[v] = true;
                        q.push(v);
                    }
                }
            }
		}

		return volt;
	};

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

	while (change) {
		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: 11 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51