Submission #405704

#	Time	Username	Problem	Language	Result	Execution time	Memory
405704		rqi	Toy Train (IOI17_train)	C++14	15 / 100	2075 ms	1452 KiB

train

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

typedef vector<int> vi;
typedef pair<int, int> pi;

const int MOD = 1e9+7;

#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define pb push_back

void ckmin(pi& a, pi b){
	a = min(a, b);
}

void ckmax(pi& a, pi b){
	a = max(a, b);
}

const int mx = 5005;
int n, m;
vi a, r, u, v;
vi adj[mx];
array<pi, mx> dp;
array<pi, mx> ndp;
int trans_ans[mx];

vi cur_ans;
void genCurAns(int node){
	assert(trans_ans[node] != -1);
	assert(cur_ans[node] > 1);
	// cout << "node: " << node << "\n";
	// for(int i = 0; i < n; i++){
	// 	cout << "cur_ans[" << i << "]: " << cur_ans[i] << "\n";
	// }
	if(cur_ans[trans_ans[node]] <= 1){
		cur_ans[node] = cur_ans[trans_ans[node]];
		return;
	}
	cur_ans[node] = 3;
	if(cur_ans[trans_ans[node]] == 2){
		genCurAns(trans_ans[node]);
		cur_ans[node] = cur_ans[trans_ans[node]];
		return;
	}
	else{
		assert(cur_ans[trans_ans[node]] == 3);
		int sum = r[node];
		int cur_node = trans_ans[node];
		while(cur_node != node){
			sum+=r[cur_node];
			cur_node = trans_ans[cur_node];
		}
		if(sum >= 1){
			cur_ans[node] = 1;
		}
		else{
			cur_ans[node] = 0;
		}
		return;
	}
}

vi getAnsFromTrans(){
	cur_ans = vi(n, 2);
	for(int i = 0; i < n; i++){
		if(cur_ans[i] == 2){
			genCurAns(i);
		}
	}
	return cur_ans;
}

vi who_wins(vi _a, vi _r, vi _u, vi _v) {
	a = _a;
	r = _r;
	u = _u;
	v = _v;
	n = sz(a);
	m = sz(u);
	for(int i = 0; i < m; i++){
		adj[u[i]].pb(v[i]);
	}

	for(int i = 0; i < n; i++){
		dp[i] = mp(0, -1);
	}
	for(int rep = 0; rep < 10005; rep++){
		for(int i = 0; i < n; i++){
			if(a[i]){
				ndp[i] = mp(-MOD, -1);
			}
			else{
				ndp[i] = mp(MOD, -1);
			}
		}
		for(int i = 0; i < n; i++){
			if(a[i]){
				for(int& u: adj[i]){
					ckmax(ndp[i], mp(dp[u].f, u));
				}
			}
			else{
				for(int& u: adj[i]){
					ckmin(ndp[i], mp(dp[u].f, u));
				}
			}
			if(r[i]){
				ndp[i].f++;
			}
		}
		swap(dp, ndp);
	}

	vi ans(n, 0);
	for(int i = 0; i < n; i++){
		if(dp[i].f > 2000){
			ans[i] = 1;
		}
	}
	return ans;
	for(int i = 0; i < n; i++){
		cout << i << " " << dp[i].f << " " << dp[i].s << "\n";
	}

	for(int i = 0; i < n; i++){
		trans_ans[i] = dp[i].s;
		cout << "i, trans[i]: " << i << " " << trans_ans[i] << "\n";
		assert(trans_ans[i] != -1);
	}
	return getAnsFromTrans();
}

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