Submission #1238515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238515		mychecksedad	Toy Train (IOI17_train)	C++20	100 / 100	163 ms	1864 KiB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define all(x) x.begin(),x.end()
const int N = 5005;

int n, m, id[N], res[N];
vi ans;
vi g[N], R[N], t[N], t2[N];
bitset<N> vis, E[N];
vi ord, ch, tp;
vector<vi> C;
void dfs(int v){
	vis[v] = 1;
	for(int u: g[v]){
		if(!vis[u]) dfs(u);
	}
	ord.pb(v);
}
void dfs2(int v){
	vis[v] = 1;
	C.back().pb(v);
	for(int u: R[v]){
		if(!vis[u]) dfs2(u);
	}
}

void solv(int i){
	// solve the i-th s

	// for(int x: C[i]) cerr << x << ' ';
	// cerr << "\n\n";

	if(C[i].size() == 1){
		// solve by itself I guess
		int v = C[i][0];
		if(tp[v] == 1){
			ans[v] = 0;
			for(int u: g[v]){
				if(u==v && ch[v]){
					ans[v] = 1;
					break;
				}
				if(ans[u]){
					ans[v] = 1;
					break;
				}
			}
		}else{
			ans[v] = 0;
			int tot = 0;
			for(int u: g[v]){
				if(u == v && ch[v] == 1){
					tot++;
				}else{
					tot += ans[u];
				}
			}
			if(tot == (int)g[v].size()){
				ans[v] = 1;
			}
		}
		return;
	}

	for(int j = 0; j < n; ++j) res[j] = -1;

	queue<int> q;
	for(int v: C[i]){
		for(int u: g[v]){
			if(u == v){
				if(tp[u] == 0){
					if(ch[u] == 0) res[v] = 0;
				}else{
					if(ch[v]){
						res[v] = 1;
					}
				}
			}
			if(id[u] != id[v]){
				// that means u is processsed
				if(tp[v] == ans[u]){
					// cerr << v << ' ' << ans[u] << ' ' << u << " crap\n";
					res[v] = ans[u];
				}
			}
		}
		if(res[v] == 1) q.push(v);
	}
	// for(int v: C[i]){
	// 	if(ch[v] == 0 && res[v] != 1) continue;
	// 	q.push(v);
	// 	if(res[v] == 1) fine[v] = 1;
	// }
	vi deg(n);
	
	for(int u: C[i]){
		if(tp[u]) deg[u] = 1;
		else{
			if(res[u] == 0) deg[u] = 1000000; // we cant really use this guy
			else{
				deg[u] = g[u].size(); 
				for(int x: g[u]) if(id[x] != id[u]) --deg[u];
			}
		}
	}
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(int u: R[v]){
			deg[u]--;
			if(deg[u] == 0){
				res[u] = 1;
				q.push(u);
			}
		}
	}
	// we distributed the lower nodes result I guess
	// now we need to use the chargers..
	for(int v: C[i]){
		if(ch[v] && res[v] != 0){
			// we gotta apply this guy
			// deg.clear();
			// deg.resize(n, -1);
			// vector<int> fine(n, -1);
			// q.push(v);
			// if(res[v] == 1) continue; // already used...
			// for(int u: C[i]){
			// 	if(tp[u] || res[u] == 1) deg[u] = 1;
			// 	else{
			// 		if(res[u] == 0) deg[u] = 1000000; // we cant really use this guy
			// 		else{
			// 			deg[u] = g[u].size(); 
			// 			for(int x: g[u]){
			// 				if(id[x] != id[u]) --deg[u];
			// 				else if(res[x] == 1) --deg[u];
			// 			}
			// 			if(deg[u]==0) q.push(u), deg[u] = -1, fine[u] = 1, assert(false);
			// 		}
			// 	}
			// 	// cerr << u << ' ' << deg[u] << " w\n";
			// }
			// while(!q.empty()){
			// 	int vv = q.front();
			// 	q.pop();
			// 	for(int u: R[vv]){
			// 		if(res[vv] != 1 || tp[u]){
			// 			deg[u]--;
			// 		}
			// 		if(deg[u] == 0){
			// 			fine[u] = 1;
			// 			deg[u] = -1;
			// 			q.push(u);
			// 		}
			// 	}
			// }
			// if(fine[v] == 1){
			// 	for(int u: C[i]) if(fine[u]) res[u] = 1;
			// }
			// for(int u: )
		}
	}



	// now we got all res, don't we?
	for(int u: C[i]) if(res[u] == -1) res[u] = 0;


	for(int v: C[i]) ans[v] = res[v];
}


std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	ch = r;
	tp = a;
	n = a.size();
	m = u.size();

	for(int i = 0; i < m; ++i){
		g[u[i]].pb(v[i]);
		R[v[i]].pb(u[i]);
	}

	// for(int i = 0; i < n; ++i){
	// 	if(!vis[i]){
	// 		dfs(i);
	// 	}
	// }
	// reverse(all(ord));
	// vis = 0;
	// for(int v: ord){
	// 	if(!vis[v]){
	// 		C.pb(vi{});
	// 		dfs2(v);
	// 		for(int x: C.back()) id[x] = int(C.size())-1;
	// 		// for(int x: C.back()) cerr << x << ' ';
	// 		// cerr << '\n';
	// 	}
	// }
	// vi deg(n);
	// for(int i = 0; i < m; ++i){
	// 	if(id[u[i]] != id[v[i]]){
	// 		if(!E[id[u[i]]][id[v[i]]]){
	// 			t[id[u[i]]].pb(id[v[i]]);
	// 			t2[id[v[i]]].pb(id[u[i]]);
	// 			E[id[u[i]]][id[v[i]]] = 1;
	// 			deg[id[u[i]]]++;
	// 		}
	// 	}
	// }
	// ans.resize(n);
	// queue<int> q;
	// for(int i = 0; i < (int)C.size(); ++i) if(deg[i] == 0) q.push(i);
	
	// while(!q.empty()){
	// 	int x = q.front(); q.pop();

	// 	solv(x);

	// 	for(int y: t2[x]){
	// 		deg[y]--;
	// 		if(deg[y] == 0){
	// 			q.push(y);
	// 		}
	// 	}
	// }		
	ans.resize(n);
	vi deg(n);
	queue<int> q;
	vi res(n, -1);
	vi CH;
	for(int u = 0; u < n; ++u){
		if(ch[u]) CH.pb(u);
		if(tp[u]) deg[u] = 1;
		else{
			deg[u] = g[u].size(); 
		}
	}
	bool ok = true;
	while(ok){
		ok = false;
		vi vis(n, 0);
		for(int x: CH) q.push(x), vis[x] = 1;
		while(!q.empty()){
			int v = q.front();
			q.pop();
			for(int u: R[v]){
				deg[u]--;
				if(deg[u] == 0){
					res[u] = 1;
					if(vis[u] == 0)
						q.push(u);
				}
			}
		}
		for(int i = 0; i < CH.size(); ++i){
			if(res[CH[i]] != 1){
				CH.erase(CH.begin() + i);
				ok = true;
				break;
			}
		}
		if(!ok){
			for(int i = 0; i < n; ++i) if(res[i] == 1) ans[i] = 1;
			break;
		}
		for(int u = 0; u < n; ++u){
			res[u] = -1;
			if(tp[u]) deg[u] = 1;
			else{
				deg[u] = g[u].size(); 
			}
		}

	}
	


	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