Submission #1225470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225470		Hamed_Ghaffari	Toy Train (IOI17_train)	C++20	100 / 100	470 ms	2212 KiB

train

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

const int MXN = 5005;

int n;
vector<int> A, R, adj[MXN], g[MXN];
bool mark[MXN], vis[MXN];
int cnt[MXN];

void add(int v, vector<int> &V, bool own) {
	if(cnt[v]<0) return;
	cnt[v] = -1;
	V.push_back(v);
	for(int u : g[v])
		if(!mark[u] && cnt[u]>0) {
			cnt[u]--;
			if(A[u]==own) add(u, V, own);
			else if(cnt[u]==0) add(u, V, own);
		}
}

inline void extend(vector<int> &V, bool own) {
	fill(cnt, cnt+n, 0);
	for(int i=0; i<n; i++)
		if(!mark[i])
			for(int j : g[i])
				cnt[j]++;
	vector<int> tmp;
	while(!V.empty()) {
		tmp.push_back(V.back());
		V.pop_back();
	}
	for(int v : tmp) add(v, V, own);
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V) {
	::A = A;
	::R = R;
	n = A.size();
	for(int i=0; i<U.size(); i++) {
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
		g[V[i]].push_back(U[i]);
	}
	vector<int> ans(n, 0);
	while(1) {
		vector<int> V, V1;
		for(int i=0; i<n; i++)
			if(!mark[i]) {
				V.push_back(i);
				if(R[i]) V1.push_back(i);
			}
		extend(V1, 1);
		if(V1.size()==V.size()) {
			for(int v : V) ans[v] = 1;
			break;
		}
		for(int v : V) vis[v] = 0;
		for(int v : V1) vis[v] = 1;
		V1.clear();
		for(int v : V)
			if(!vis[v])
				V1.push_back(v);
		extend(V1, 0);
		for(int v : V1) mark[v] = 1;
	}
	return ans;
}

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