Submission #70731

#	Time	Username	Problem	Language	Result	Execution time	Memory
70731		Kmcode	Toy Train (IOI17_train)	C++14	0 / 100	132 ms	2208 KiB

train

#include <bits/stdc++.h>

using namespace std;


//#include "train.h"

vector<int> v[5002];
vector<int> rv[5002];
bool use[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;
	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]])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 (stderr)

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

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