oj.uz

Submission #70852

# Submission time Handle Problem Language Result Execution time Memory
70852 2018-08-23T14:16:16 Z Kmcode Toy Train (IOI17_train) C++14
0 / 100
 749 ms 1904 KB 
#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]]==false&&sz[belong[node]]>1)return true;
	for(int go:v[node]){
		if(us[go]!=u_s){
			if(a_walk(go))return true;
		}
	}
	return false;
}
inline bool b_walk(int node){
	us[node]=u_s;
	if(bor[node])return true;
	if(sz[belong[node]]>1)return true;
	for(int go:v[node]){
		if(us[go]!=u_s){
			if(b_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;
		}
      		if(r[u1[i]]||r[v1[i]])continue;
		v[u1[i]].push_back(v1[i]);
		rv[v1[i]].push_back(u1[i]);
	}
	scc();
	for(int i=0;i<n;i++){
		ok[belong[i]]|=r1[i];
	}
	vector<int> ret(a1.size(),1);
  	for(int i=0;i<n;i++)v[i].clear();
  	for(int i=0;i<u1.size();i++)v[u1[i]].push_back(v1[i]);
	for(int i=0;i<n;i++){
		u_s++;
		if(a_walk(i)){
			ret[i]=0;
		}
	}
	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:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u1.size();i++){
              ~^~~~~~~~~~
train.cpp:110:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<u1.size();i++)v[u1[i]].push_back(v1[i]);
                ~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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