Submission #1238328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238328		mychecksedad	Toy Train (IOI17_train)	C++20	16 / 100	158 ms	5448 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;
	}

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

	queue<int> q;
	for(int v: C[i]){
		for(int u: g[v]){
			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(); 
		}
	}
	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, 0);
			vector<int> fine(n, -1);
			q.push(v);
			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(); 
				}
			}
			while(!q.empty()){
				int v = q.front();
				q.pop();
				for(int u: R[v]){
					deg[u]--;
					if(deg[u] == 0){
						fine[u] = 1;
						q.push(u);
					}
				}
			}
			if(fine[v] == 1){
				for(int u: C[i]) if(fine[u]) res[u] = 1;
			}
		}
	}



	// 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);
			}
		}
	}		



	return ans;
}
// please pass 5th subtask

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