Submission #167882

#	Time	Username	Problem	Language	Result	Execution time	Memory
167882		dolphingarlic	Toy Train (IOI17_train)	C++14	0 / 100	8 ms	1528 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[3000];
bool arezou[3000], charging[3000], in_f[2][3000], visited[2][3000];
int f_cnt[2];

void dfs(int node, int step) {
	visited[step][node] = true;
	for (int i : graph[node]) {
		if (!visited[step][i]) dfs(i, step);
		in_f[step][node] |= in_f[step][i];
	}
	if (in_f[step][node]) f_cnt[step]++;
}

void solve(vector<int> stations) {
	for (int i : stations) visited[0][i] = visited[1][i] = in_f[0][i] = in_f[1][i] = false;
	f_cnt[0] = f_cnt[1] = 0;

	for (int i : stations) if (charging[i]) {
		visited[0][i] = in_f[0][i] = true;
		f_cnt[0]++;
	}
	for (int i : stations) if (!visited[0][i]) dfs(i, 0);
	if (f_cnt[0] == stations.size()) {
		for (int i : stations) res[i] = true;
		return;
	}

	for (int i : stations) if (!in_f[0][i]) {
		visited[1][i] = in_f[1][i] = true;
		f_cnt[1]++;
	}
	for (int i : stations) if (!visited[1][i]) dfs(i, 1);
	if (f_cnt[1] == stations.size()) return;

	vector<int> new_stations;
	for (int i : stations) if (!in_f[1][i]) new_stations.push_back(i);
	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:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (f_cnt[0] == stations.size()) {
      ~~~~~~~~~^~~~~~~~~~~~~~~~~~
train.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (f_cnt[1] == stations.size()) return;
      ~~~~~~~~~^~~~~~~~~~~~~~~~~~

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