Submission #423145

#	Time	Username	Problem	Language	Result	Execution time	Memory
423145		Rudy420	Toy Train (IOI17_train)	C++17	28 / 100	305 ms	1568 KiB

train

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define lg length()
#define pb push_back
#define INF 2000000005
#define LINF 1000000000000000005
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
#include "train.h"

int n,m;

vector <vector<int>> g, h;

int count_ones(vector<int> &a){
	int ans = 0;
	for(int i=0;i<n;i++){
		ans += a[i];
	}
	return ans;
}

void f(vector<int> &s, vector<int> &w, vector<int> &a, int id){
	queue<int> q;
	vector<int> d(n);
	for(int i=0;i<n;i++){
		if(s[i]) q.push(i);
		d[i] = sz(g[i]);
	}
	while(sz(q)){
		int i = q.front();
		q.pop();
		for(int j : h[i]){
			if(!w[j] || s[j]) continue;
			d[j]--;
			if(a[j] == id || d[j] == 0){
				s[j] = 1;
				q.push(j);
			}
		}
	}
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = sz(a);
	m = sz(u);
	vector<int> ans(n, 1);
	for(int i=0;i<n;i++) g.pb({}), h.pb({});
	for(int i=0;i<m;i++) g[u[i]].pb(v[i]), h[v[i]].pb(u[i]);

	vector<int> s(n);
	while(1){
		for(int i=0;i<n;i++){
			if(r[i] && ans[i]) s[i] = 1;
			else s[i] = 0;
		}
		f(s, ans, a, 1);
		if(count_ones(s) == count_ones(ans)) break;
		for(int i=0;i<n;i++){
			if(!s[i] && ans[i]) s[i] = 1;
			else s[i] = 0;
		}
		f(s, ans, a, 0);
		for(int i=0;i<n;i++){
			if(s[i]) ans[i] = 0;
		}
	}

	return ans;
}

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