Submission #358911

#	Time	Username	Problem	Language	Result	Execution time	Memory
358911		Kerim	Toy Train (IOI17_train)	C++17	100 / 100	815 ms	4012 KiB

train

#include "train.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int col[MAXN],vis[MAXN],who[MAXN],mark[MAXN],n,m;
int deg[MAXN],ban[MAXN];
vector<int>adj[MAXN];
vector<int> operator - (vector<int>a,vector<int>b){
	vector<int>c;
	tr(it,b)mark[*it]=1;
	tr(it,a)if(!mark[*it])c.pb(*it);
	tr(it,b)mark[*it]=0;
	return c;
}
vector<int>f(int me,vector<int>S){
	for(int i=0;i<n;i++)vis[i]=deg[i]=0;
	queue<int>q;
	tr(it,S)q.push(*it),vis[*it]=1;	
	for(int i=0;i<n;i++){
		if(ban[i])continue;
		tr(it,adj[i])
			if(!ban[*it])
				deg[*it]++;
	}
	while(!q.empty()){
		int nd=q.front();q.pop();
		tr(it,adj[nd]){
			if(ban[*it] or vis[*it])
				continue;
			if(who[*it]==me)
				vis[*it]=1,q.push(*it);	
			else{
				if(--deg[*it]==0)
					vis[*it]=1,q.push(*it);	
			}
		}
	}
	vector<int>res;
	for(int i=0;i<n;i++)
		if(!ban[i] and vis[i])
			res.pb(i);
	return res;
}
vector<int> who_wins(vector<int> a, vector<int> r,vector<int> u,vector<int> v) {
	n=int(a.size());m=int(u.size());
	for(int i=0;i<n;i++)col[i]=r[i],who[i]=a[i];
	for(int i=0;i<m;i++)
		adj[v[i]].pb(u[i]);
	vector<int>cur,f_a,f_b;
	for(int i=0;i<n;i++)
		cur.pb(i);
	while(!cur.empty()){
		vector<int>X;
		tr(it,cur)if(r[*it])X.pb(*it);
		f_a=f(1,X);
		f_b=f(0,cur-f_a);
		if(f_b.empty())break;
		cur=cur-f_b;tr(it,f_b)ban[*it]=1;
	}
	vector<int>ans(n,0);
	tr(it,cur)ans[*it]=1;
	return ans;
}

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