제출 #1238453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238453		mychecksedad	Toy Train (IOI17_train)	C++20	16 / 100	153 ms	5444 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;
			}
		}
	}



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

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