Submission #409514

#	Time	Username	Problem	Language	Result	Execution time	Memory
409514		rqi	Toy Train (IOI17_train)	C++14	100 / 100	994 ms	1888 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
#define bk back()

#define all(x) begin(x), end(x)

const int mx = 5005;
int n, m;
vi a, r, u, v;
vi adj[mx];
vi radj[mx];
bool bad[mx];

int getBType(){

	for(int i = 0; i < n; i++){
		if(bad[i]) continue;
		if(a[i] == 1){
			bool works = 1;
			for(auto u: adj[i]){
				if(!bad[u]){
					works = 0;
					break;
				}
			}
			if(works){
				return i;
			}
		}
		else{
			for(auto u: adj[i]){
				if(bad[u]){
					return i;
				}
			}
		}
	}
	//cout << "getB Over" << "\n";
	return -1;
}

array<bool, mx> dp;
array<bool, mx> ndp;
bool forced[mx];
int cur_deg[mx]; //number of neighbors that can be forced into a good C
int bad_cur_deg[mx];
int self[mx];
 
queue<int> to_unForce;
 
void iForce(int node){
	//cout << "iForce: " << node << "\n";
	for(auto u: radj[node]){
		if(forced[u] || bad[u]) continue;
		if(a[u] == 0){
			cur_deg[u]++;
			//cout << u << " " << cur_deg[u] << "\n";
			if(cur_deg[u] == sz(adj[u])){
				forced[u] = 1;
				to_unForce.push(u);
			}
		}
		else{
			forced[u] = 1;
			to_unForce.push(u);
		}
	}
}
 
void initForce(){
	for(int i = 0; i < n; i++){
		forced[i] = 0;
		cur_deg[i] = 0;
	}
	for(int i = 0; i < n; i++){
		if(bad[i]) continue;
		if(r[i] == 1){
			if(!forced[i]){
				forced[i] = 1;
				to_unForce.push(i);
			}
		}
	}
 
	while(sz(to_unForce)){
		int node = to_unForce.front();
		to_unForce.pop();
		iForce(node);
	}
}

int getAType(){
	
	initForce();
	for(int i = 0; i < n; i++){
		if(!bad[i] && !forced[i] && a[i] == 1){
			return i;
		}
	}

	//cout << "getA over" << "\n";
	return -1;
}

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]);
		radj[v[i]].pb(u[i]);
	}
	for(int i = 0; i < n; i++){
		for(auto u: adj[i]){
			if(u == i) self[i]++;
		}
	}

	for(int i = 0; i < n; i++){
		dp[i] = 1;
		if(r[i] == 1) dp[i] = 0;
	}
	for(int rep = 0; rep < mx; rep++){
		for(int i = 0; i < n; i++){
			ndp[i] = 0;
		}
		for(int i = 0; i < n; i++){
			if(r[i] == 1) continue;
			if(a[i] == 1){
				ndp[i] = 1;
				for(auto u: adj[i]){
					if(dp[u] == 0) ndp[i] = 0;
				}
			}
			else{
				ndp[i] = 0;
				for(auto u: adj[i]){
					if(dp[u] == 1) ndp[i] = 1;
				}
			}
		}
		swap(dp, ndp);
	}

	for(int i = 0; i < n; i++){
		if(dp[i] == 1){
			bad[i] = 1;
			//cout << "initial bad: " << i << "\n";
		}
	}

	while(true){
		int node = getBType();
		if(node == -1){
			node = getAType();
		}
		if(node == -1) break;
		//cout << "node: " << node << "\n";
		bad[node] = 1;
	}

	vi ans(n, 0);
	for(int i = 0; i < n; i++){
		if(!bad[i]){
			ans[i] = 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