Submission #1196996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196996		alterio	Toy Train (IOI17_train)	C++20	0 / 100	63 ms	832 KiB

train

#include <bits/stdc++.h>
#include "train.h"

using namespace std;

const int mxn = 15;

int n, m;
vector<int> a, r, g[mxn], A, B;
int nxt[mxn];

bool trip(int start) {
	bool visited[mxn];
	memset(visited, 0, sizeof(visited));
	int cur = start, energy = n;
	while (energy && !visited[cur]) {
		visited[cur] = 1;
		energy--;
		if (nxt[cur] == cur) return r[cur];
		cur = nxt[cur];
		if (r[cur]) energy = n;
	}
	return (energy > 0);
}

bool check(int start) {
	int vals[B.size() + 1];
	memset(vals, 0, sizeof(vals));
	while (vals[0] < g[B[0]].size()) {
		int cnt = 0;
		for (auto x : B) {
			nxt[x] = g[x][vals[cnt++]];
		}
		if (!trip(start)) return 0;
		int ind = B.size() - 1;
		vals[ind]++;
		while (ind > 0 && vals[ind] >= g[B[ind]].size()) {
			vals[ind] = 0;
			vals[ind - 1]++;
			ind--;
		}
	}
	return 1;
}

bool solve(int start) {
	int vals[A.size() + 1];
	memset(vals, 0, sizeof(vals));
	while (vals[0] < g[A[0]].size()) {
		int cnt = 0;
		for (auto x : A) {
			nxt[x] = g[x][vals[cnt++]];
		}
		if (check(start)) return 1;
		int ind = A.size() - 1;
		vals[ind]++;
		while (ind > 0 && vals[ind] >= g[A[ind]].size()) {
			vals[ind] = 0;
			vals[ind - 1]++;
			ind--;
		}
	}
}

vector<int> who_wins(vector<int> _a, vector<int> _r, vector<int> u, vector<int> v) {
	a = _a, r = _r;
	n = a.size(), m = u.size();
	for (int i = 0; i < n; i++) {
		if (a[i]) A.push_back(i);
		else B.push_back(i);
	}
	for (int i = 0; i < m; i++) g[u[i]].push_back(v[i]);
	vector<int> res(n, 0);
	for (int i = 0; i < n; i++) {
		res[i] = solve(i);
	}
	return res;
}

Compilation message (stderr)

train.cpp: In function 'bool solve(int)':
train.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
   63 | }
      | ^

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