Submission #116307

#	Time	Username	Problem	Language	Result	Execution time	Memory
116307		nvmdava	장난감 기차 (IOI17_train)	C++17	100 / 100	828 ms	1792 KiB

train

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

vector<int> &a = *(new vector<int>), &r = *(new vector<int>), &u = *(new vector<int>), &v = *(new vector<int>);
int n, m;

vector<int> res, pos, to[5005], fr[5005];

bool in[5005], proc[5005];
int dem[5005];

queue<int> q;
void f(int st){
	memset(in, 0, sizeof in);
	memset(dem, 0, sizeof dem);
	
	for(int i = 0; i < m; i++)
		if(proc[u[i]] | proc[v[i]] == 0)
			dem[u[i]]++;
			
	while(!q.empty()){
		int v = q.front();
		q.pop();
		if(in[v]) continue;
		in[v] = 1;
		for(int x : fr[v]){
			if(proc[x]) continue;
			dem[x]--;
			if(in[x]) continue;
			if(a[x] == st)
				q.push(x);
			else if(!dem[x])
				q.push(x);
		}
	}
}


bool solve(){
//	cerr<<"SOLVE BEGIN\n";
	for(int x : pos)
		if(r[x]) q.push(x);
	f(1);
	
	for(int x : pos)
		if(!in[x]) q.push(x);
	f(0);
	
	bool ret = 0;
	for(int i = pos.size() - 1; i >= 0; i--){
		if(in[pos[i]] == 1){
			proc[pos[i]] = 1;
			swap(pos[i], pos.back());
			pos.pop_back();
			ret = 1;
		}
	}
	return ret;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	for(int i = (m = u.size()) - 1; i >= 0; i--)
		fr[v[i]].push_back(u[i]);
	
	for(int i = (n = a.size()) - 1; i >= 0; i--)
		pos.push_back(i);
	
	::a = a;
	::r = r;
	::v = v;
	::u = u;
	
	res.resize(n);
	while(solve());
	
	for(int x : pos)
		res[x] = 1;
	
	return res;
}

Compilation message (stderr)

train.cpp: In function 'void f(int)':
train.cpp:19:30: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   if(proc[u[i]] | proc[v[i]] == 0)
                   ~~~~~~~~~~~^~~~

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