Submission #262138

#	Time	Username	Problem	Language	Result	Execution time	Memory
262138		sjimed	Toy Train (IOI17_train)	C++14	100 / 100	934 ms	1912 KiB

train

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

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define pre(a) cout << fixed; cout.precision(a)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define em emplace
#define eb emplace_back
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
vector<int> g[5010];
vector<int> rg[5010];
vector<int> w;
vector<int> A;

vector<bool> canGo(vector<int> &x, int c) {
	int deg[5010] = {};
	vector<bool> chk(n, 0);
	vector<int> ret;
	queue<int> q;

	for(int i=0; i<n; i++) {
		if(w[i] != -1) continue;

		for(int j : g[i]) 
			if(w[j] == -1) deg[i]++;
	}

	for(auto i : x) 
		chk[i] = true, q.em(i);

	while(q.size()) {
		int cur = q.front();
		q.pop();

		for(auto i : rg[cur]) {
			if(chk[i] || w[i] != -1) continue;
			if(A[i] == c) {
				chk[i] = true;
				q.em(i);
			}
			else {
				deg[i]--;
				if(deg[i] == 0) chk[i] = true, q.em(i);
			}
		}
	}

	for(int i=0; i<n; i++)
		if(chk[i]) ret.eb(i);

	return chk;
}

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

	w.resize(n, -1);

	for(int i=0; i<m; i++) {
		g[u[i]].eb(v[i]);
		rg[v[i]].eb(u[i]);
	}

	int cnt = 1;
	while(cnt) {
		vector<int> x, y;
		for(int i=0; i<n; i++) 
			if(r[i] && w[i] == -1) x.eb(i);

		auto v = canGo(x, 1);

		for(int i=0; i<n; i++) 
			if(w[i] == -1 && !v[i]) y.eb(i);

		if(y.empty()) {
			for(int i=0; i<n; i++) 
				if(w[i] == -1) w[i] = 1;
			
			break;
		}
		else {
			v = canGo(y, 0);
			for(int i=0; i<n; i++) 
				if(v[i]) w[i] = 0;
		}
	}

	return w;
}

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