Submission #417532

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
417532	2021-06-03T21:20:52 Z	ja_kingy	Toy Train (IOI17_train)	C++14	0 / 100	337 ms	1428 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	972 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	332 KB	3rd lines differ - on the 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	1404 KB	Output is correct
2	Correct	199 ms	1404 KB	Output is correct
3	Correct	337 ms	1428 KB	Output is correct
4	Incorrect	8 ms	1320 KB	3rd lines differ - on the 13th token, expected: '1', found: '0'
5	Halted	0 ms	0 KB	-