Submission #577171

#	Time	Username	Problem	Language	Result	Execution time	Memory
577171		HIR180	Toy Train (IOI17_train)	C++17	100 / 100	436 ms	1700 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n = a.size();
	vector<int> res(n);
	vector<vector<int>>edge(n), redge(n);
	rep(i, u.size()){
		edge[u[i]].pb(v[i]);
		redge[v[i]].pb(u[i]);
	}
	while(1){
		vector<int>zan(n), ok(n), in(n);
		rep(i, n) ok[i] = edge[i].size();
		queue<int>que;
		vector<int>frst(n);
		int idx = 0;
		rep(i, n) if(r[i]){
			que.push(i);
			frst[i] = 1;
			idx++;
		}
		while(!que.empty()){
			int q = que.front(); que.pop();
			idx--;
			if(idx < 0 and in[q] and frst[q]) continue;
			for(auto ot:redge[q]){
				ok[ot] --;
				if(!in[ot] and (!ok[ot] or a[ot])){
					que.push(ot);
					in[ot] = 1;
				}
			}
		}
		bool upd = 0;
		rep(i, n){
			if(r[i] and !in[i]){
				r[i] = 0;
				upd = 1;
			}
		}
		if(!upd){
			rep(i, n) res[i] = in[i];
			return res;
		}
	}
}

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:4:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,n) for(int i=0;i<n;i++)
......
   11 |  rep(i, u.size()){
      |      ~~~~~~~~~~~               
train.cpp:11:2: note: in expansion of macro 'rep'
   11 |  rep(i, u.size()){
      |  ^~~

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