Submission #409416

#	Time	Username	Problem	Language	Result	Execution time	Memory
409416		rqi	Toy Train (IOI17_train)	C++14	39 / 100	866 ms	2152 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];

int to_in[mx];
int to_out[mx];

bool visited[mx];
vi order;

void dfs1(int node){
	if(a[node] == 0 || r[node] == 1) return;
	for(auto u: adj[node]){
		if(!visited[u]){
			visited[u] = 1;
			dfs1(u);
		}
	}
	order.pb(node);
}

vector<vi> comps;
vi comp;

void dfs2(int node){
	if(a[node] == 0 || r[node] == 1) return;
	comp.pb(node);
	for(auto u: radj[node]){
		if(!visited[u]){
			visited[u] = 1;
			dfs2(u);
		}
	}
}

void reduceAStrong(){ 
	//create new adj, remove self edges for AN
	for(int i = 0; i < n; i++){
		visited[i] = 0;
	}
	for(int i = 0; i < n; i++){
		if(!visited[i]){
			visited[i] = 1;
			dfs1(i);
		}
	}
	for(int i = 0; i < n; i++){
		visited[i] = 0;
	}
	reverse(all(order));
	for(auto u: order){
		if(!visited[u]){
			comp.clear();
			visited[u] = 1;
			dfs2(u);
			comps.pb(comp);
		}
	}

	for(int i = 0; i < n; i++){
		adj[i].clear();
		radj[i].clear();
	}

	for(auto COMP: comps){
		// cout << "COMP: ";
		// for(auto u: COMP){
		// 	cout << u << " ";
		// }
		// cout << "\n";
		for(int i = 0; i < sz(COMP); i++){
			to_in[COMP[i]] = COMP[0];
			to_out[COMP[i]] = COMP.bk;
			if(i+1 < sz(COMP)){
				adj[COMP[i]].pb(COMP[i+1]);
			}
		}
	}

	for(int i = 0; i < m; i++){
		int A = u[i];
		int B = v[i];
		if(a[A] == 1 && r[A] == 0){
			A = to_out[A];
		}
		if(a[B] == 1 && r[B] == 0){
			B = to_in[B];
		}


		if((a[A] == 1 && r[A] == 0) && (a[B] == 1 && r[B] == 0) && to_in[A] == to_in[B]){ //remove self edge
			continue;
		}
		adj[A].pb(B);
	}

	for(int i = 0; i < n; i++){
		for(auto u: adj[i]){
			radj[u].pb(i);
		}
	}

}

array<bool, mx> dp;
array<bool, mx> ndp;

bool bad[mx];
int cur_deg[mx]; //for A

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]);
	}
	reduceAStrong();

	// for(int i = 0; i < n; i++){
	// 	cout << i << ": ";
	// 	for(auto u: adj[i]){
	// 		cout << u << ", ";
	// 	}
	// 	cout << "\n";
	// }

	queue<int> q;

	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++){
		cur_deg[i] = sz(adj[i]);
		if(dp[i] == 1){
			q.push(i);
			bad[i] = 1;
		}
	}
	while(sz(q)){
		int node = q.front();
		q.pop();
		for(auto u: radj[node]){
			if(bad[u]) continue;
			if(a[u] == 1){
				cur_deg[u]--;
				if(cur_deg[u] == 0){
					bad[u] = 1;
					q.push(u);
				}
			}
			else{
				bad[u] = 1;
				q.push(u);
			}
		}
	}

	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: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 0 / 51