Submission #1034775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034775		ALeonidou	Toy Train (IOI17_train)	C++17	0 / 100	37 ms	2908 KiB

train

#include "train.h"
#include <bits/stdc++.h>

using namespace std;

#define ll int
#define sz(x) (ll)x.size()
#define endl "\n"
#define pb push_back
#define F first
#define S second

typedef vector <ll> vi;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;

#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(vi &v){
	for (ll i =0; i<sz(v); i++){
		cout<<v[i]<<" ";
	}
	cout<<endl;
}

void printVct2D(vector <vi> &adj){
	cout<<endl;
	for (ll i =0; i<sz(adj); i++){
		cout<<i<<": ";
		for (ll j =0; j<sz(adj[i]); j++){
			cout<<adj[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}

vector <vi> adj, radj, cadj, fadj;
vi cadj_type;	//0: neutral, 1:charged, 2: not charged
vi vis;
vi r,a,u,v;
stack <ll> st;
void dfs(ll u){
	vis[u] = 1;
	for (ll i= 0; i<sz(adj[u]); i++){
		if (!vis[adj[u][i]]){
			dfs(adj[u][i]);
		}
	}
	st.push(u);
}

void dfs2(ll u){
	vis[u] = sz(cadj);
	cadj.back().pb(u);
	if (r[u]) cadj_type.back() = 1;
	for (ll i =0; i<sz(radj[u]); i++){
		ll c = radj[u][i];
		if (!vis[c]){
			dfs2(c);
		}
		else if (vis[c] < sz(cadj)){
			fadj[vis[c]-1].pb(sz(cadj)-1);
		}
	}
}

bool can_reach_neutral_dfs(ll u, ll p = -1){
	if (cadj_type[u] == 2) return true;
	for (ll i =0; i<sz(fadj[u]); i++){
		ll c = fadj[u][i];
		if (c != p){
			if (can_reach_neutral_dfs(c, u)){
				return true;
			}
		}
	}
	return false;
}

vi vis2;
bool dfs_hidden_type_2(ll u, set <ll> &st){
	// dbg(u);
	vis2[u] = 1;
	for (ll i =0; i<sz(adj[u]); i++){
		ll c = adj[u][i];
		if (st.find(c) != st.end() && !r[c]){
			if (vis2[c]) return true;
			else{
				if (dfs_hidden_type_2(c, st)) return true;
			}
		}
	}
	return false;
}

vi who_wins(vi A, vi R, vi U, vi V) {
	r = R, a = A, u = U, v = V;;
	ll n = sz(a), m = sz(u);
	
	adj.assign(n,vi());
	radj.assign(n, vi());
	vi self_cycles(n, 0);
	for(ll i =0; i<m; i++){
		if (v[i] == u[i]) self_cycles[v[i]] = 1;
		adj[u[i]].pb(v[i]);
		radj[v[i]].pb(u[i]);
	}

	vis.assign(n, 0);
	for (ll i =0; i<n; i++){
		if (!vis[i]){
			dfs(i);
		}
	}

	vis.assign(n, 0);
	while (!st.empty()){
		ll f = st.top();
		st.pop();
		if (vis[f]) continue;
		cadj.pb(vi());
		fadj.pb(vi());
		cadj_type.pb(0);
		dfs2(f);
		if (cadj_type.back() == 0){
			if (sz(cadj.back()) > 1 || self_cycles[cadj.back().back()]){
				cadj_type.back() = 2;
			}
		}
		else if (sz(cadj.back()) == 1 && !self_cycles[cadj.back().back()]){
			cadj_type.back() = 0;
		}
		else{
			//validate for type 1
			set <ll> st;
			for (ll i =0; i<sz(cadj.back()); i++) st.insert(cadj.back()[i]);
			vis2.assign(n, 0);
			for (ll i =0; i<sz(cadj.back()); i++){
				// dbg2(i, cadj.back()[i]);
				if (!vis2[cadj.back()[i]] && !r[cadj.back()[i]] && dfs_hidden_type_2(cadj.back()[i], st)){
					cadj_type.back() = 2;
					// cout<<"-------------"<<endl;
					break;
				}
			}
		}
	}

	// printVct(self_cycles);
	// printVct2D(cadj);
	// printVct(cadj_type);
	// printVct2D(fadj);
	
	vi ans(n, 1);
	for (ll i =0; i<sz(cadj); i++){
		if (can_reach_neutral_dfs(i, -1)){
			for (ll j = 0; j<sz(cadj[i]); j++){
				ans[cadj[i][j]] = 0;
			}
		}
	}
	
	return ans;
}


/*
7 10
1 1 1 1 1 1 1
0 1 0 0 0 1 1
0 2
0 1
2 3
1 4
4 5
5 3
3 4
3 6
6 6
4 4

7 9
1 1 1 1 1 1 1
0 1 0 0 0 1 0
0 2
0 1
2 3
1 4
4 5
5 3
3 4
3 6
6 6

5 7
0 0 0 0 0
0 1 0 0 0
0 1
1 2
2 3
3 2
3 1
2 4
4 4
*/

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