제출 #978876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978876		Lalic	장난감 기차 (IOI17_train)	C++17	100 / 100	516 ms	1644 KiB

train

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

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int N;
vector<int> adj[5005];

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	N=(int)a.size();
	
	vector<int> ans(N, 1);
	for(int i=0;i<(int)u.size();i++){
		adj[v[i]].pb(u[i]);
	}
	
	auto recalc = [&]() -> void{
		vector<int> rem(N, 0), gin(N, 0);
		
		for(auto val : u) gin[val]++;
		
		queue<int> q;
		for(int i=0;i<N;i++){
			if(r[i] && ans[i]){
				q.push(i);
				rem[i]=1;
			}
		}
		
		while(!q.empty()){
			int curr=q.front();
			q.pop();
			
			for(auto at : adj[curr]){
				if(rem[at]) continue;
				
				gin[at]--;
				if(a[at] || !gin[at]){
					rem[at]=1;
					q.push(at);
				}
			}
		}
		
		for(int i=0;i<N;i++){
			if(!rem[i]){
				ans[i]=0;
				q.push(i);
			}
		}
		
		gin.assign(N, 0);
		for(auto val :  u) gin[val]++;
		
		while(!q.empty()){
			int curr=q.front();
			q.pop();
			
			for(auto at : adj[curr]){
				if(!ans[at]) continue;
				
				gin[at]--;
				if(!a[at] || !gin[at]){
					ans[at]=0;
					q.push(at);
				}
			}
		}
	};
	
	vector<int> bef(N, 0);
	while(bef!=ans){
		bef=ans;
		recalc();
	}
	
	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