Submission #74063

#	Time	Username	Problem	Language	Result	Execution time	Memory
74063		Bruteforceman	Toy Train (IOI17_train)	C++11	100 / 100	708 ms	9660 KiB

train

#include "train.h"
#include "bits/stdc++.h"
using namespace std;
vector <int> g[5005];
vector <int> trans[5005];

int own[5005];
int charge[5005];
int n;
int m;

int out[5005];
bool take[5005];
bool del[5005];
int outdeg[5005];

vector <int> Fa(vector <int> v) {
	for(int i = 0; i < n; i++) {
		out[i] = 0;
		take[i] = false;
	}
	queue <int> q;
	for(auto i : v) {
		q.push(i);
		take[i] = true;
	}
	while(!q.empty()) {
		int i = q.front();
		q.pop();
		for(auto j : trans[i]) {
			if(del[j]) continue;
			out[j] += 1;
			if(!take[j] && own[j] == 1) {
				q.push(j);
				take[j] = true;
			}
			if(!take[j] && out[j] == outdeg[j] && own[j] == 0) {
				q.push(j);
				take[j] = true;
			}
		}
	}
	vector <int> ans;
	for(int i = 0; i < n; i++) {
		if(take[i]) {
			ans.emplace_back(i);
		}
	}
	return ans;
}	
vector <int> Fb(vector <int> v) {
	for(int i = 0; i < n; i++) {
		out[i] = 0;
		take[i] = false;
	}
	queue <int> q;
	for(auto i : v) {
		q.push(i);
		take[i] = true;
	}
	while(!q.empty()) {
		int i = q.front();
		q.pop();
		for(auto j : trans[i]) {
			if(del[j]) continue;
			out[j] += 1;
			if(!take[j] && own[j] == 0) {
				q.push(j);
				take[j] = true;
			}
			if(!take[j] && out[j] == outdeg[j] && own[j] == 1) {
				q.push(j);
				take[j] = true;
			}
		}
	}
	vector <int> ans;
	for(int i = 0; i < n; i++) {
		if(take[i]) {
			ans.emplace_back(i);
		}
	}
	return ans;
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	vector <int> ans;
	n = a.size();
	m = u.size();
	ans.resize(n);

	for(int i = 0; i < n; i++) {
		own[i] = a[i];
		charge[i] = r[i];
		del[i] = false;
	}
	for(int i = 0; i < m; i++) {
		int p = u[i];
		int q = v[i];
		g[p].emplace_back(q);
		trans[q].emplace_back(p);
		++outdeg[p];
	}
	while(true) {
		vector <int> station;
		for(int i = 0; i < n; i++) {
			if(charge[i] && !del[i]) {
				station.emplace_back(i);
			}
		}
		vector <int> P = Fa(station);
		vector <int> Q;
		for(int i = 0; i < n; i++) {
			if(!take[i] && !del[i]) {
				Q.emplace_back(i);
			}
		}
		if(Q.empty()) {
			for(auto i : P) {
				ans[i] = 1;
			}
			break;
		}
		vector <int> X = Fb(Q);
		for(auto i : X) {
			ans[i] = 0;
			del[i] = true;
			for(auto j : trans[i]) {
				--outdeg[j];
			}
 		}
	}
	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