Submission #1105188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105188		alexander707070	Toy Train (IOI17_train)	C++14	32 / 100	25 ms	81632 KiB

train

#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;
 
int n;
bool is[MAXN],sp[MAXN],ok[MAXN],li[MAXN],dp[MAXN],primka[MAXN],ok2[MAXN];
vector<int> v[MAXN],r[MAXN],ans,g[MAXN];
int tim[MAXN],comp[MAXN],k,sz[MAXN];
bool ban[MAXN],dead[MAXN];
stack<int> st;

void dfs(int x){
	li[x]=true;

	for(int i:v[x]){
		if(!li[i] and !ban[i])dfs(i);
	}

	st.push(x);
}

void scc(int x){
	li[x]=true;
	comp[x]=k; sz[k]++;

	if(sp[x])ok[k]=true;
	if(dead[x])ok2[k]=true;

	for(int i:r[x]){
		if(!li[i] and !ban[i])scc(i);
	}
}

bool ff(int x){
	if(li[x])return dp[x];
	li[x]=true;

	dp[x]=ok[x];
	for(int i:g[x]){
		if(ff(i))dp[x]=true;
	}

	return dp[x];
}
 
bool brute(int x,int last,int t){
	tim[x]=t;
	if(sp[x])last=t;
 
	for(int i=0;i<v[x].size();i++){
		if(is[x]){
			if(tim[v[x][i]]!=0 and tim[v[x][i]]<=last){
				tim[x]=0; return true;
			}
		}else{
			if(tim[v[x][i]]!=0 and tim[v[x][i]]>last){
				tim[x]=0; return false;
			}
		}
	}
 
	for(int i=0;i<v[x].size();i++){
		if(tim[v[x][i]]!=0)continue;
 
		if(is[x]){
			if(brute(v[x][i],last,t+1)){
				tim[x]=0; return true;
			}
		}else{
			if(!brute(v[x][i],last,t+1)){
				tim[x]=0; return false;
			}
		}
	}
 
	tim[x]=0;
	return !is[x];
}
 
vector<int> who_wins(vector<int> A,vector<int> R, vector<int> from,vector<int> to){
	n=int(A.size());
	
	int mins=1,maxs=0;
	for(int i=1;i<=n;i++){
		is[i]=A[i-1];

		mins=min(mins,int(is[i]));
		maxs=max(maxs,int(is[i]));

		sp[i]=R[i-1];
	}
 
	for(int i=1;i<=from.size();i++){
		from[i-1]++; to[i-1]++;

		v[from[i-1]].push_back(to[i-1]);
		r[to[i-1]].push_back(from[i-1]);

		if(from[i-1]==to[i-1])primka[from[i-1]]=true;
	}
 
	if(n<=15){
		for(int i=1;i<=n;i++){
			for(int f=1;f<=n;f++)tim[f]=0;
 
			if(brute(i,0,1))ans.push_back(1);
			else ans.push_back(0);
		}
	}else{
		if(mins==maxs and mins==1){

			for(int i=1;i<=n;i++){
				if(li[i])continue;
				dfs(i);
			}
 
			for(int i=1;i<=n;i++)li[i]=false;
 
			while(!st.empty()){
				if(!li[st.top()]){
					k++; scc(st.top());
 
					if(sz[k]==1 and !primka[st.top()])ok[k]=false;
				}
				st.pop();
			}
 
			for(int i=1;i<=from.size();i++){
				if(comp[from[i-1]]==comp[to[i-1]])continue;
				g[comp[from[i-1]]].push_back(comp[to[i-1]]);
			}
 
			for(int i=1;i<=n;i++)li[i]=false;
 
			for(int i=1;i<=n;i++){
				if(ff(comp[i]))ans.push_back(1);
				else ans.push_back(0);
			}
			
		}else if(mins==maxs and mins==0){

			for(int i=1;i<=n;i++){
				if(sp[i])ban[i]=true;
			}

			for(int i=1;i<=n;i++){
				if(li[i] or ban[i])continue;
				dfs(i);
			}

			for(int i=1;i<=n;i++)li[i]=false;

			while(!st.empty()){
				if(!li[st.top()]){
					k++; scc(st.top());

					if(sz[k]>1 or primka[st.top()])ok[k]=true;
					else ok[k]=false;
				}
				st.pop();
			}

			for(int i=1;i<=n;i++){
				if(!ban[i] and ok[comp[i]])dead[i]=true;
			}

			for(int i=1;i<=n;i++)li[i]=ban[i]=false;

			for(int i=1;i<=n;i++){
				if(li[i])continue;
				dfs(i);
			}

			for(int i=1;i<=n;i++)li[i]=false;

			k=0;
			while(!st.empty()){
				if(!li[st.top()]){
					k++; ok[k]=false;
					
					scc(st.top());
				}
				st.pop();
			}

			for(int i=1;i<=from.size();i++){
				if(comp[from[i-1]]==comp[to[i-1]])continue;
				g[comp[from[i-1]]].push_back(comp[to[i-1]]);
			}

			for(int i=1;i<=n;i++){
				li[i]=false; ok[i]=ok2[i];
			}

			for(int i=1;i<=n;i++){
				if(ff(comp[i]))ans.push_back(0);
				else ans.push_back(1);
			}
		}
	}
 
	return ans;
}
 
/*int main(){
 
	ans=who_wins({0, 0}, {1,0}, {0, 0, 1, 1}, {0, 1, 0, 1});
 
	for(int i:ans)cout<<i<<" ";
 
	return 0;
}*/

Compilation message (stderr)

train.cpp: In function 'bool brute(int, int, int)':
train.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
train.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:93:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i=1;i<=from.size();i++){
      |              ~^~~~~~~~~~~~~
train.cpp:128:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |    for(int i=1;i<=from.size();i++){
      |                ~^~~~~~~~~~~~~
train.cpp:186:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |    for(int i=1;i<=from.size();i++){
      |                ~^~~~~~~~~~~~~

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