Submission #409503

#	Time	Username	Problem	Language	Result	Execution time	Memory
409503		rqi	Toy Train (IOI17_train)	C++14	16 / 100	896 ms	1804 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];
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){
	for(auto u: radj[node]){
		if(forced[u]) continue;
		if(a[u] == 0){
			cur_deg[u]++;
			//cout << u << " " << cur_deg[u] << "\n";
			if(cur_deg[u] == sz(adj[u])-self[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++){
		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);
	}

	for(int i = 0; i < n; i++){
		if(forced[i]){
			cur_deg[i] = 0;
			for(auto u: adj[i]){
				if(forced[u]){
					cur_deg[i]++;
				}
			}
		}
	}
}

queue<int> q;

void unForce(int node){
	assert(forced[node] == 0);
	//cout << "unForce " << node << "\n";
	for(auto u: radj[node]){
		if(forced[u]){
			if(a[u] == 1){
				cur_deg[u]--;
				if(cur_deg[u] == 0 || (self[u] == cur_deg[u] && r[u] == 0)){
					forced[u] = 0;
					to_unForce.push(u);

					if(!bad[u] && a[u] == 1){ //second condition unnecessary
						bad[u] = 1;
						q.push(u);
					}
				}
			}
			else{
				forced[u] = 0;
				to_unForce.push(u);
			}
			
		}
	}
}

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]++;
			}
		}
	}

	initForce();

	//cout << "cur_deg[2]: " << cur_deg[2] << "\n";

	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++){
	// 	cout << i << " " << forced[i] << " " << cur_deg[i] << "\n";
	// }

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

	for(int i = 0; i < n; i++){
		if(!forced[i] && !bad[i] && a[i] == 1){ //second condition unnecessary
			q.push(i);
			bad[i] = 1;
			//cout << i << "\n";
			
		}
	}
	
	while(true){
		while(sz(to_unForce)){
			int node = to_unForce.front();
			to_unForce.pop();
			unForce(node);
		}

		if(sz(q) == 0) break;
		int node = q.front();
		q.pop();

		for(auto u: radj[node]){
			if(bad[u]) continue;
			if(a[u] == 1){
				bad_cur_deg[u]--;
				
				if(bad_cur_deg[u] == 0){
					bad[u] = 1;
					q.push(u);
				}
			}
			else{
				bad[u] = 1;
				q.push(u);
			}
		}

		if(forced[node]){
			forced[node] = 0;
			to_unForce.push(node);
		}
		
	}

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