Submission #425737

#	Time	Username	Problem	Language	Result	Execution time	Memory
425737		Tangent	Toy Train (IOI17_train)	C++17	0 / 100	10 ms	2252 KiB

train

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;

#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	int n = a.size();
	vvii adj(n), radj(n);
	rep(i, u.size()) {
		adj[u[i]].emplace_back(v[i]);
		radj[v[i]].emplace_back(u[i]);
	}

	vii vis(n), stack;
	function<void(int, int)> dfs;
	dfs = [&](int x, int p) {
		vis[x] = true;
		forin(y, adj[x]) {
			if (y != p && !vis[y]) {
				dfs(y, x);
			}
		}
		stack.emplace_back(x);
	};

	rep(i, n) {
		if (!vis[i]) {
			dfs(i, -1);
		}
	}
	
	vii comp(n, -1);
	vvii comps;
	vii hasr;
	function<void(int, int)> dfs2;
	dfs2 = [&](int x, int p) {
		comp[x] = comps.size() - 1;
		comps.back().emplace_back(x);
		if (r[x]) {
			hasr.back() = 1;
		}
		forin(y, radj[x]) {
			if (y != p && comp[y] == -1) {
				dfs2(y, x);
			}
		}
	};
	
	while (!stack.empty()) {
		int x = stack.back();
		stack.pop_back();
		if (comp[x] == -1) {
			comps.emplace_back(vii());
			hasr.emplace_back(0);
			dfs2(x, -1);
		}
	}

	vvii adj3(comps.size());
	rep(i, u.size()) {
		if (comp[u[i]] != comp[v[i]]) {
			adj3[comp[u[i]]].emplace_back(comp[v[i]]);
		}
	}

	function<void(int, int)> dfs3;
	dfs3 = [&](int x, int p) {
		forin(y, adj3[x]) {
			dfs3(y, x);
			hasr[x] = max(hasr[x], hasr[y]);
		}
	};

	vii res(n);
	rep(i, n) {
		res[i] = hasr[comp[i]];
	}
	return res;
}

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