제출 #296237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296237		b00n0rp	장난감 기차 (IOI17_train)	C++17	0 / 100	13 ms	1920 KiB

train

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

#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)

const int MAXN = 5005;

int n,m;
int indeg[MAXN];
vi adj[MAXN],rev[MAXN];
vi ans;

vi charging,own;

vi f(vi tot,vi sub,int type){
	for(auto x:tot){
		indeg[x] = rev[x].size();
		if(own[x] == type) indeg[x] = 1;
	}
	queue<int> q;
	for(auto x:sub){
		indeg[x] = 0;
		q.push(x);
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto v:rev[u]){
			indeg[v]--;
			if(!indeg[v]){
				sub.pb(v);
				q.push(v);
			}
		}
	}
	return sub;
}

void solve(vi gg){
	// cout << gg.size() << endl;
	// for(auto x:gg) cout << x << " "; cout << endl;
	if(gg.empty()) return;

	vi ch,win,lose,nwin,nlose;
	for(auto x:gg){
		if(charging[x]) ch.pb(x);
	}
	win = f(gg,ch,1);
	if(win.size() == gg.size()){
		for(auto x:gg) ans[x] = 1;
		return;
	}
	bitset<MAXN> w;
	for(auto x:win) w[x] = 1;
	for(auto x:gg){
		if(!w[x]) nwin.pb(x);
	}
	lose = f(gg,nwin,0);
	w.reset();
	for(auto x:lose){
		w[x] = 1;
		ans[x] = 0;
	}
	for(auto x:gg){
		if(!w[x]) nlose.pb(x);
	}
	solve(nlose);
}

vi who_wins(vi a, vi r, vi u, vi v){
	charging = r;
	own = a;
	n = a.size();
	m = u.size();
	REP(i,m){
		adj[u[i]].pb(v[i]);
		rev[v[i]].pb(u[i]);
	}
	ans.resize(n);
	vi gg;
	REP(i,n) gg.pb(i);
	solve(gg);
	return ans;
}

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