Submission #775991

#	Time	Username	Problem	Language	Result	Execution time	Memory
775991		ttamx	Toy Train (IOI17_train)	C++14	16 / 100	9 ms	2004 KiB

train

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

using namespace std;

const int N=5005;
const int M=20005;

int n,m;
int a[N],r[N];
int vis[N];
vector<int> adj[N],radj[N];
vector<int> ans;
stack<int> st;
vector<vector<int>> scc;
int sccid[N];
int deg[N],del[N];
bool lose[N],win[N];
bool selfloop[N];
queue<int> q;

void scc1(int u,bool block=true){
	if(vis[u])return;
	vis[u]=true;
	for(auto v:adj[u])if(!block||!r[v])scc1(v,block);
	st.emplace(u);
}

void scc2(int u,bool block=true){
	if(vis[u])return;
	vis[u]=true;
	scc.back().emplace_back(u);
	sccid[u]=scc.size();
	for(auto v:radj[u])if(!block||!r[v])scc2(v,block);
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V) {
	n=A.size();
	m=U.size();
    ans.resize(n);
	for(int i=0;i<n;i++)a[i]=A[i],r[i]=R[i];
    for(int i=0;i<m;i++){
        int u=U[i],v=V[i];
		if(u==v)selfloop[u]=true;
		else{
        	adj[u].emplace_back(v);
        	radj[v].emplace_back(u);
			deg[u]++;
		}
    }
	// cerr << "LOSE\n";
	for(int i=0;i<n;i++)vis[i]=false;
	for(int i=0;i<n;i++)if(!r[i])scc1(i);
	for(int i=0;i<n;i++)vis[i]=false;
	while(!st.empty()){
		auto u=st.top();
		st.pop();
		if(vis[u])continue;
		scc.emplace_back(vector<int>(0));
		scc2(u);
	}
	for(auto com:scc){
		bool ok=true;
		for(auto u:com){
			if(a[u]==0)continue;
			for(auto v:adj[u]){
				if(sccid[v]!=sccid[u]){
					ok=false;
					break;
				}
			}
			if(!ok)break;
		}
		if(com.size()==1&&!selfloop[com[0]])ok=false;
		// for(auto u:com)cerr << u << " ";
		// cerr << ": " << ok << "\n";
		if(ok)for(auto u:com)lose[u]=true;
	}
	// for(int i=0;i<n;i++)cerr << lose[i] << " \n"[i==n-1];
	for(int i=0;i<n;i++)if(lose[i])q.emplace(i);
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		for(auto v:radj[u]){
			del[v]++;
			if(lose[v])continue;
			if(a[v]==0||(del[v]==deg[v]&&!(selfloop[v]&&r[v]))){
				lose[v]=true;
				q.emplace(v);
			}
		}
	}
	// for(int i=0;i<n;i++)cerr << lose[i] << " \n"[i==n-1];
	// cerr << "WIN\n";
	scc.clear();
	for(int i=0;i<n;i++)vis[i]=false;
	for(int i=0;i<n;i++)scc1(i,false);
	for(int i=0;i<n;i++)vis[i]=false;
	while(!st.empty()){
		auto u=st.top();
		st.pop();
		if(vis[u])continue;
		scc.emplace_back(vector<int>(0));
		scc2(u,false);
	}
	for(auto com:scc){
		bool ok=true,ok2=false;
		for(auto u:com){
			if(r[u]==1)ok2=true;
			if(a[u]==1)continue;
			for(auto v:adj[u]){
				if(sccid[v]!=sccid[u]){
					ok=false;
					break;
				}
			}
			if(!ok)break;
		}
		ok&=ok2;
		if(com.size()==1&&!selfloop[com[0]])ok=false;
		// for(auto u:com)cerr << u << " ";
		// cerr << ": " << ok << "\n";
		if(ok)for(auto u:com)if(!lose[u])win[u]=true;
	}
	// for(int i=0;i<n;i++)cerr << win[i] << " \n"[i==n-1];
	for(int i=0;i<n;i++)if(win[i])q.emplace(i);
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		for(auto v:radj[u]){
			del[v]++;
			if(win[v])continue;
			if(a[v]==1||(del[v]==deg[v]&&!lose[v]&&!(selfloop[v]&&!r[v]))){
				win[v]=true;
				q.emplace(v);
			}
		}
	}
	// for(int i=0;i<n;i++)cerr << win[i] << " \n"[i==n-1];
	for(int i=0;i<n;i++)ans[i]=win[i]&&!lose[i];
	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