Submission #646611

#	Time	Username	Problem	Language	Result	Execution time	Memory
646611		jamezzz	Toy Train (IOI17_train)	C++17	100 / 100	1086 ms	1888 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

#define maxn 5005
#define pb push_back
typedef vector<int> vi;

int n,m,cnt[maxn];
bool done[maxn],added[maxn],in[maxn];
vi RAL[maxn],AL[maxn],a,r,u,v,ans;

void expand(vi &v,int p){
	for(int i=0;i<n;++i){
		cnt[i]=AL[i].size();
		added[i]=false;
	}
	vi toadd;
	for(int x:v){
		toadd.pb(x);
		added[x]=true;
	}
	while(!toadd.empty()){
		int u=toadd.back();
		toadd.pop_back();
		for(int v:RAL[u]){
			--cnt[v];
			if(!added[v]&&(a[v]==p||cnt[v]==0)){
				toadd.pb(v);
				added[v]=true;
			}
		}
	}
	v.clear();
	for(int i=0;i<n;++i){
		if(added[i])v.pb(i);
	}
}

bool step(){
	int rem=0;
	vi charge;
	for(int i=0;i<n;++i){
		if(done[i])continue;
		AL[i].clear();
		RAL[i].clear();
		in[i]=false;
		++rem;
		if(r[i]==1)charge.pb(i);
	}
	if(rem==0)return false;
	for(int i=0;i<m;++i){
		if(!done[u[i]]&&!done[v[i]]){
			AL[u[i]].pb(v[i]);
			RAL[v[i]].pb(u[i]);
		}
	}
	expand(charge,1);
	
	if(charge.size()==rem){
		for(int x:charge)ans[x]=1;
		return false;
	}
	
	for(int x:charge)in[x]=true;
	vector<int> other;
	for(int i=0;i<n;++i){
		if(!done[i]&&!in[i])other.pb(i);
	}
	expand(other,0);
	for(int x:other)done[x]=true;
	return true;
}

vi who_wins(vi _a,vi _r,vi _u,vi _v){
	a=_a,r=_r,u=_u,v=_v;
	n=a.size(),m=u.size();
	ans.resize(n);
	while(step());
	return ans;
}

Compilation message (stderr)

train.cpp: In function 'bool step()':
train.cpp:60:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |  if(charge.size()==rem){
      |     ~~~~~~~~~~~~~^~~~~

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