Submission #70836

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
70836	2018-08-23T14:00:40 Z	Kmcode	Toy Train (IOI17_train)	C++14	11 / 100	811 ms	5416 KB

train

#include <bits/stdc++.h>
 
using namespace std;
 
 
//#include "train.h"
 
vector<int> v[5002];
vector<int> rv[5002];
bool use[5002];

int sz[5002];

vector<int> bc;
inline void dfs(int b){
	use[b]=true;
	for(int go:v[b]){
		if(use[go]==false){
			dfs(go);
		}
	}
	bc.push_back(b);
}
int belong[5002];
inline void dfs2(int b,int be){
	use[b]=false;
	belong[b]=be;
  	sz[be]++;
	for(int go:rv[b]){
		if(use[go]){
			dfs2(go,be);
		}
	}
}
 
int m;
int n;
 
void scc(){
	for(int i=0;i<n;i++){
		if(use[i]==false){
			dfs(i);
		}
	}
	reverse(bc.begin(),bc.end());
	for(int i=0;i<bc.size();i++){
		if(use[bc[i]]){
			dfs2(bc[i],m);
			m++;
		}
	}
}
vector<int> ed[5002];
bool ok[5002];
 
int us[5002];
int u_s;
 
bool bor[5002];
bool are[5002];
vector<int> r;



inline bool a_walk(int node){
	us[node]=u_s;
	if(are[node])return true;
	if(ok[belong[node]]&&sz[belong[node]]>1)return true;
	for(int go:v[node]){
		if(us[go]!=u_s){
			if(a_walk(go))return true;
		}
	}
	return false;
}
 
std::vector<int> who_wins(std::vector<int> a1, std::vector<int> r1, std::vector<int> u1, std::vector<int> v1) {
	r=r1;
	n=a1.size();
	for(int i=0;i<u1.size();i++){
		if(u1[i]==v1[i]){
			if(r1[u1[i]]){
				are[u1[i]]=true;
			}
			else{
				bor[u1[i]]=true;
			}
			continue;
		}
		v[u1[i]].push_back(v1[i]);
		rv[v1[i]].push_back(u1[i]);
	}
	scc();
	for(int i=0;i<n;i++){
		for(int go:v[i]){
			if(belong[i]!=belong[go]){
				ed[belong[i]].push_back(belong[go]);
			}
		}
	}
	for(int i=0;i<m;i++){
		sort(ed[i].begin(),ed[i].end());
		ed[i].erase(unique(ed[i].begin(),ed[i].end()),ed[i].end());
	}
	for(int i=0;i<n;i++){
		ok[belong[i]]|=r1[i];
	}
	vector<int> ret(a1.size(),0);
	for(int i=0;i<n;i++){
		u_s++;
		if(a_walk(i)){
			ret[i]=1;
		}
	}
	return ret;
}

Compilation message

train.cpp: In function 'void scc()':
train.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<bc.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:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u1.size();i++){
              ~^~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	8 ms	1528 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	1528 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	327 ms	2156 KB	Output is correct
2	Correct	317 ms	2452 KB	Output is correct
3	Correct	381 ms	2548 KB	Output is correct
4	Correct	17 ms	2688 KB	Output is correct
5	Correct	61 ms	2924 KB	Output is correct
6	Correct	811 ms	3292 KB	Output is correct
7	Correct	18 ms	3404 KB	Output is correct
8	Correct	202 ms	3516 KB	Output is correct
9	Correct	505 ms	3796 KB	Output is correct
10	Correct	99 ms	3868 KB	Output is correct
11	Correct	269 ms	4060 KB	Output is correct
12	Correct	38 ms	4124 KB	Output is correct
13	Correct	16 ms	4508 KB	Output is correct
14	Correct	16 ms	4772 KB	Output is correct
15	Correct	15 ms	4980 KB	Output is correct
16	Correct	14 ms	5128 KB	Output is correct
17	Correct	15 ms	5336 KB	Output is correct
18	Correct	464 ms	5416 KB	Output is correct