Submission #1105106

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1105106	2024-10-25T11:58:56 Z	alexander707070	Toy Train (IOI17_train)	C++14	21 / 100	114 ms	151844 KB

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];
vector<int> v[MAXN],r[MAXN],ans,g[MAXN];
int tim[MAXN],comp[MAXN],k,sz[MAXN];
stack<int> st;

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

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

	st.push(x);
}

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

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

	for(int i:r[x]){
		if(!li[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 cout<<1/0;
	}
 
	return ans;
}
 
/*int main(){
 
	ans=who_wins({0, 1}, {1, 0}, {0, 0, 1, 1}, {0, 1, 0, 1});
 
	for(int i:ans)cout<<i<<" ";
 
	return 0;
}*/

Compilation message

train.cpp: In function 'bool brute(int, int, int)':
train.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
train.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  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:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i=1;i<=from.size();i++){
      |              ~^~~~~~~~~~~~~
train.cpp:126:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |    for(int i=1;i<=from.size();i++){
      |                ~^~~~~~~~~~~~~
train.cpp:137:16: warning: division by zero [-Wdiv-by-zero]
  137 |   }else cout<<1/0;
      |               ~^~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	101 ms	151304 KB	Execution killed with signal 4
2	Halted	0 ms	0 KB	-

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	76368 KB	Output is correct
2	Correct	12 ms	76368 KB	Output is correct
3	Correct	12 ms	76368 KB	Output is correct
4	Correct	12 ms	76368 KB	Output is correct
5	Correct	12 ms	76368 KB	Output is correct
6	Correct	12 ms	76368 KB	Output is correct
7	Correct	12 ms	76536 KB	Output is correct
8	Correct	12 ms	76280 KB	Output is correct
9	Correct	12 ms	76368 KB	Output is correct
10	Correct	12 ms	76368 KB	Output is correct
11	Correct	12 ms	76536 KB	Output is correct
12	Correct	12 ms	76368 KB	Output is correct
13	Correct	12 ms	76368 KB	Output is correct
14	Correct	12 ms	76368 KB	Output is correct
15	Correct	12 ms	76368 KB	Output is correct
16	Correct	12 ms	76368 KB	Output is correct
17	Correct	13 ms	76368 KB	Output is correct
18	Correct	13 ms	76368 KB	Output is correct
19	Correct	12 ms	76536 KB	Output is correct
20	Correct	13 ms	76380 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	77816 KB	Output is correct
2	Correct	19 ms	77800 KB	Output is correct
3	Correct	19 ms	77660 KB	Output is correct
4	Correct	21 ms	77392 KB	Output is correct
5	Correct	20 ms	77392 KB	Output is correct
6	Correct	25 ms	77392 KB	Output is correct
7	Correct	19 ms	77392 KB	Output is correct
8	Correct	20 ms	77408 KB	Output is correct
9	Correct	19 ms	77392 KB	Output is correct
10	Correct	19 ms	77392 KB	Output is correct
11	Correct	19 ms	77404 KB	Output is correct
12	Correct	24 ms	77392 KB	Output is correct
13	Correct	21 ms	77376 KB	Output is correct
14	Correct	20 ms	77392 KB	Output is correct
15	Correct	20 ms	77692 KB	Output is correct
16	Correct	20 ms	77392 KB	Output is correct
17	Correct	20 ms	77532 KB	Output is correct
18	Correct	18 ms	77136 KB	Output is correct