Submission #70848

#	Time	Username	Problem	Language	Result	Execution time	Memory
70848		Kmcode	Toy Train (IOI17_train)	C++14	0 / 100	1566 ms	2112 KiB

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;
}
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++){
		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++)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]=1;
		}
	}
	return ret;
}

Compilation message (stderr)

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:121: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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51