Submission #163180

#	Time	Username	Problem	Language	Result	Execution time	Memory
163180		Minnakhmetov	장난감 기차 (IOI17_train)	C++14	100 / 100	918 ms	1684 KiB

train

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

using namespace std;

#define all(aaa) aaa.begin(), aaa.end();
#define ll long long

const int N = 5005;
vector<int> g[N];
int deg[N], tmp[N];
bool used[N];
int n, m;

vector<int> reachable(vector<int> &a, vector<int> v, int master) {
	for (int i = 0; i < n; i++) {
		used[i] = 0;
		tmp[i] = deg[i];
	}

	queue<int> q;

	auto check = [&](int x) {
		if (!used[x]) {
			if (a[x] == master) {
				used[x] = 1;
				q.push(x);
			}
			else if (--tmp[x] == 0) {
				used[x] = 1;
				q.push(x);
			}
		}
	};

	for (int x : v) {
		used[x] = 1;
		q.push(x);
	}

	while (!q.empty()) {
		int node = q.front();
		q.pop();

		for (int to : g[node]) {
			check(to);
		}
	}

	vector<int> ans;
	for (int i = 0; i < n; i++) {
		if (used[i])
			ans.push_back(i);
	}

	return ans;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = a.size(), m = u.size();

	for (int i = 0; i < m; i++) {
		g[v[i]].push_back(u[i]);
		deg[u[i]]++;
	}

	vector<int> res(n, 1);

	bool work = true;

	while (work) {
		work = false;

		vector<int> sts;
		for (int i = 0; i < n; i++) {
			if (r[i])
				sts.push_back(i);
		}

		vector<int> good = reachable(a, sts, 1), killers;

		// cout << "G : ";
		// for (int x : good) {
		// 	cout << x << " ";
		// }
		// cout << "\n";

		for (int i = 0, j = 0; i < n; i++) {
			while (j < good.size() && good[j] < i)
				j++;
			if (j == good.size() ||
				good[j] != i)
				killers.push_back(i);
		}
		vector<int> bad = reachable(a, killers, 0);

		// cout << "K : ";
		// for (int x : killers) {
		// 	cout << x << " ";
		// }
		// cout << "\n";

		// cout << "B : ";
		// for (int x : bad) {
		// 	cout << x << " ";
		// }
		// cout << "\n";

		for (int x : bad) {
			if (r[x])
				work = true;
			res[x] = 0;
			r[x] = 0;
		}
	}

	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:89:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (j < good.size() && good[j] < i)
           ~~^~~~~~~~~~~~~
train.cpp:91:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (j == good.size() ||
        ~~^~~~~~~~~~~~~~

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