Submission #1310087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310087		lnw143	Toy Train (IOI17_train)	C++17	100 / 100	380 ms	1556 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
const int N=5005;
int n,m;
vi e[N],g[N];
bool f[N];
int c[N],t[N];
vi who_wins(vi a,vi r,vi u,vi v) {
	n=a.size(),m=u.size();
	for(int i=0; i<m; ++i) e[u[i]].push_back(v[i]);
	for(int i=0; i<m; ++i) g[v[i]].push_back(u[i]);
	for(int i=0; i<n; ++i) t[i]=a[i]?1:e[i].size();
	while(1) {
		for(int i=0; i<n; ++i) f[i]=0;
		queue<int> Q;
		for(int i=0; i<n; ++i) {
			c[i]=0;
			for(auto j : e[i]) if(r[j]) ++c[i];
			if(c[i]>=t[i]) f[i]=1,Q.push(i);
		}
		for(; Q.size(); Q.pop()) {
			int u=Q.front();
			if(r[u]) continue;
			for(auto v : g[u])
				if(!f[v]&&++c[v]>=t[v]) {
					f[v]=1;
					Q.push(v);
				}
		}
		bool ok=0;
		for(int i=0; i<n; ++i)
			if(!f[i]&&r[i])
				r[i]=0,ok=1;
		if(!ok) break;
	}
	vector<int> res(n);
	for(int i=0; i<n; ++i) res[i]=f[i];
	return res;
}

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