Submission #112295

#	Time	Username	Problem	Language	Result	Execution time	Memory
112295		gs14004	장난감 기차 (IOI17_train)	C++17	26 / 100	268 ms	1536 KiB

train

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

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
	vector<int> gph[5005];
	int n = a.size();
	int m = u.size();
	vector<int> ret(n);
	vector<int> proc(n);
	for(int i=0; i<m; i++){
		gph[v[i]].push_back(u[i]);
	}
	while(true){
		int unproc = count(proc.begin(), proc.end(), 0);
		if(unproc == 0) break;
		vector<int> deg(n);
		queue<int> que;
		for(int i=0; i<m; i++){
			if(!proc[u[i]] && !proc[v[i]]){
				deg[u[i]]++;
			}
		}
		for(int i=0; i<n; i++){
			if(!proc[i] && r[i]){
				deg[i] = 0;
				que.push(i);
			}
		}
		vector<int> aReach;
		while(!que.empty()){
			int x = que.front(); que.pop();
			aReach.push_back(x);
			for(auto &j : gph[x]){
				if(proc[j]) continue;
				if(a[j] == 1 && deg[j] > 0){
					deg[j] = 0;
					que.push(j);
				}
				if(a[j] == 0){
					deg[j]--;
					if(deg[j] == 0) que.push(j);
				}
			}
		}
		if(aReach.size() == unproc){
			for(auto &i : aReach) proc[i] = 1, ret[i] = 1;
		}
		else{
			fill(deg.begin(), deg.end(), 0);
			for(int i=0; i<m; i++){
				if(!proc[u[i]] && !proc[v[i]]){
					deg[u[i]]++;
				}
			}
			vector<int> rem(n);
			for(auto &i : aReach) rem[i] = 1;
			for(int i=0; i<n; i++){
				if(!proc[i] && !rem[i]){
					que.push(i);
				}
			}
			while(!que.empty()){
				int x = que.front(); que.pop();
				proc[x] = 1;
				ret[x] = 0;
				for(auto &j : gph[x]){
					if(proc[j]) continue;
					if(a[j] == 0 && deg[j] > 0){
						deg[j] = 0;
						que.push(j);
					}
					if(a[j] == 1){
						deg[j]--;
						if(deg[j] == 0) que.push(j);
					}
				}
			}
		}
	}
	return ret;
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(aReach.size() == unproc){
      ~~~~~~~~~~~~~~^~~~~~~~~

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