제출 #834185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834185		KoD	장난감 기차 (IOI17_train)	C++17	0 / 100	2066 ms	1236 KiB

train

#include "train.h"

#include <array>
#include <algorithm>
#include <numeric>
#include <utility>
#include <iterator>
#include <iostream>
#include <cassert>
#include <tuple>
#include <string>
#include <set>
#include <vector>
#include <queue>
#include <map>

using std::array;
using std::tuple;
using std::pair;
using std::vector;
using std::string;

using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;

template <class T> bool setmin(T& x, const T& y) { return x > y && (x = y, true); }
template <class T> bool setmax(T& x, const T& y) { return x < y && (x = y, true); }

template <class F> struct make_fixed : private F {
    explicit make_fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V) {
	const int N = (int)A.size();
	const int M = (int)U.size();
	vector<vector<int>> rG(N);
	for (int i = 0; i < M; ++i) {
		rG[V[i]].push_back(U[i]);
	}
	vector<int> ans(N);
	vector<bool> alive(N, true);
	std::queue<int> que;
	while (std::any_of(alive.begin(), alive.end(), [](bool b) { return b; })) {
		for (int i = 0; i < N; ++i) {
			if (alive[i] && A[i] == R[i]) {
				ans[i] = A[i];
				alive[i] = false;
				que.push(i);
			}
		}
		while (!que.empty()) {
			const int u = que.front();
			que.pop();
			for (const int v : rG[u]) {
				if (alive[v] && A[v] == ans[u]) {
					ans[v] = A[v];
					alive[v] = false;
					que.push(v);
				}
			}
		}
		vector<int> As;
		for (int i = 0; i < N; ++i) {
			if (alive[i] && A[i]) {
				As.push_back(i);
			}
		}
		if (As.empty()) {
			for (int i = 0; i < N; ++i) {
				if (alive[i]) {
					ans[i] = 1;
				}
			}
			break;
		}
		vector<char> done(N);
		for (int i = 0; i < M; ++i) {
			int u = U[i], v = V[i];
			if (A[u] && !A[v] && alive[u] && alive[v] && !done[u]) {
				done[u] = true;
				que.push(u);
			}
		}
		while (!que.empty()) {
			const int u = que.front();
			que.pop();
			for (const int v : rG[u]) {
				if (alive[v] && !done[v] && A[v]) {
					done[v] = true;
					que.push(v);
				}
			}
		}
		bool found = false;
		for (const int u : As) {
			if (!done[u]) {
				found = true;
				ans[u] = 0;
				que.push(u);
			}
		}
		if (!found) {
			for (const int u : As) {
				ans[u] = 1;
				que.push(u);
			}
		}
	}
	return ans;
}

#ifndef EVAL
#include "grader.cpp"
#endif

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