Submission #417532

#	Time	Username	Problem	Language	Result	Execution time	Memory
417532		ja_kingy	Toy Train (IOI17_train)	C++14	0 / 100	337 ms	1428 KiB

train

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

int n, used[5000];
vector<int> adj[5000], a;
vector<int> force(vector<int> f, int p) {
	vector<int> res,deg(n);
	for (int i = 0; i < n; ++i) {
		for (int j: adj[i]) if (!used[j]) deg[i]++;
	}
	for (int i: f) used[i] = 1;
	while (f.size()) {
		int u = f.back(); f.pop_back();
		res.push_back(u);
		for (int v: adj[u]) {
			if (!used[v]) {
				deg[v]--;
				if (a[v] == p || !deg[v]) {
					used[v] = 1;
					f.push_back(v);
				}
			}
		}
	}
	return res;
}

vector<int> who_wins(vector<int> _a, vector<int> r, vector<int> u, vector<int> v) {
	a = _a;
	n = a.size();
	for (int i = 0; i < u.size(); ++i) {
		adj[u[i]].push_back(v[i]);
	}
	vector<int> res(n);
	for (;;) {
		vector<int> chargers, rem;
		for (int i = 0; i < n; ++i) if (!used[i]){
			rem.push_back(i);
			if (r[i]) chargers.push_back(i);
		} 
		vector<int> fa = force(chargers, 1);
		if (fa.size() == rem.size()) {
			for (int i: rem) res[i] = 1;
			break;
		} else {
			vector<int> s, in_fa(n);
			for (int i: fa) in_fa[i] = 1;
			for (int i: rem) {
				used[i] = 0;
				if (!in_fa[i]) s.push_back(i); 
			}
			vector<int> fb = force(s, 0);
			if (fb.size() == rem.size()) break;
		}
	}
	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:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i = 0; i < u.size(); ++i) {
      |                  ~~^~~~~~~~~~

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