Submission #167884

#	Time	Username	Problem	Language	Result	Execution time	Memory
167884		dolphingarlic	Toy Train (IOI17_train)	C++14	5 / 100	339 ms	37960 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

vector<int> res, graph[5000];
bool arezou[5000], charging[5000], inactive[5000];
bool in_f_a[5000], in_f_b[5000], visited_a[5000], visited_b[5000];
int f_a, f_b;

void dfs_a(int node) {
	visited_a[node] = true;
	bool possible = true;
	for (int i : graph[node]) {
		if (inactive[i]) continue;
		if (!visited_a[i]) dfs_a(i);
		
		if (arezou[node]) in_f_a[node] |= in_f_a[i];
		else possible &= in_f_a[i];
	}
	if (!arezou[node]) in_f_a[node] = possible;
	if (in_f_a[node]) f_a++;
}
void dfs_b(int node) {
	visited_b[node] = true;
	bool possible = true;
	for (int i : graph[node]) {
		if (inactive[i]) continue;
		if (!visited_b[i]) dfs_b(i);
		
		if (!arezou[node]) in_f_b[node] |= in_f_b[i];
		else possible &= in_f_b[i];
	}
	if (arezou[node]) in_f_b[node] = possible;
	if (in_f_b[node]) f_b++;
}

void solve(vector<int> stations) {
	for (int i : stations) visited_a[i] = visited_b[i] = in_f_a[i] = in_f_b[i] = false;
	f_a = f_b = 0;

	for (int i : stations) if (charging[i]) {
		visited_a[i] = in_f_a[i] = true;
		f_a++;
	}
	for (int i : stations) if (!visited_a[i]) dfs_a(i);
	if (f_a == stations.size()) {
		for (int i : stations) res[i] = true;
		return;
	}

	for (int i : stations) if (!in_f_a[i]) {
		visited_b[i] = in_f_b[i] = true;
		f_b++;
	}
	for (int i : stations) if (!visited_b[i]) dfs_b(i);
	if (f_b == stations.size()) return;

	vector<int> new_stations;
	for (int i : stations) {
		if (!in_f_b[i]) new_stations.push_back(i);
		else inactive[i] = true;
	}
	solve(new_stations);
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n = a.size(), m = u.size();
	res.resize(n);
	FOR(i, 0, m) graph[u[i]].push_back(v[i]);
	FOR(i, 0, n) arezou[i] = a[i], charging[i] = r[i];

	vector<int> stations(n);
	FOR(i, 0, n) stations[i] = i;
	solve(stations);
	return res;
}

Compilation message (stderr)

train.cpp: In function 'void solve(std::vector<int>)':
train.cpp:47:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (f_a == stations.size()) {
      ~~~~^~~~~~~~~~~~~~~~~~
train.cpp:57:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (f_b == stations.size()) return;
      ~~~~^~~~~~~~~~~~~~~~~~

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