Submission #790270

#	Time	Username	Problem	Language	Result	Execution time	Memory
790270		Valaki2	Toy Train (IOI17_train)	C++14	11 / 100	229 ms	1732 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int maxn = 5000;

int n, m;
vector<int> g[1 + maxn], rg[1 + maxn];
int own[1 + maxn], charge[1 + maxn];
bool has_self[1 + maxn];

bool good[1 + maxn];

vector<int> top;
int comp[1 + maxn];
bool vis[1 + maxn];
int comp_cnt;
int comp_size[1 + maxn];

void dfs_1(int cur) {
	if(charge[cur]) {
		return;
	}
	vis[cur] = true;
	for(int nei : g[cur]) {
		if(!vis[nei]) {
			dfs_1(nei);
		}
	}
	top.pb(cur);
}

void dfs_2(int cur) {
	if(charge[cur]) {
		return;
	}
	comp[cur] = comp_cnt;
	for(int nei : rg[cur]) {
		if(comp[nei] == 0) {
			dfs_2(nei);
		}
	}
}

void scc() {
	for(int i = 1; i <= n; i++) {
		if(!vis[i]) {
			dfs_1(i);
		}
	}
	reverse(top.begin(), top.end());
	for(int cur : top) {
		if(comp[cur] == 0) {
			comp_cnt++;
			dfs_2(cur);
		}
	}
	for(int i = 1; i <= n; i++) {
		comp_size[comp[i]]++;
	}
	/*for(int i = 1; i <= n; i++) {
		cout << comp[i] << " ";
	}
	cout << endl;
	for(int i = 1; i <= comp_cnt; i++) {
		cout << comp_size[i] << " ";
	}
	cout << endl;*/
	for(int i = 1; i <= n; i++) {
		if(charge[i] != 1 && (comp_size[comp[i]] != 1 || has_self[i])) {
			good[i] = true;
		}
	}
}

void mark_good() {
	for(int iter = 1; iter <= n - 1; iter++) {
		for(int i = 1; i <= n; i++) {
			if(good[i]) {
				for(int j : rg[i]) {
					good[j] = true;
				}
			}
		}
	}
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = a.size();
	m = u.size();
	for(int i = 0; i < m; i++) {
		g[u[i] + 1].pb(v[i] + 1);
		rg[v[i] + 1].pb(u[i] + 1);
		if(u[i] == v[i]) {
			has_self[u[i] + 1] = true;
		}
	}
	for(int i = 1; i <= n; i++) {
		own[i] = a[i - 1];
		charge[i] = r[i - 1];
	}
	scc();
	mark_good();
	vector<int> res(n);
	for(int i = 0; i < n; i++) {
		res[i] = !good[i + 1];
	}
	return res;
}

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