제출 #834317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834317		KoD	장난감 기차 (IOI17_train)	C++17	100 / 100	698 ms	1320 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<int> ans(N);
	vector<char> alive(N, true);
	vector<vector<int>> rG(N);
	for (int i = 0; i < M; ++i) {
		rG[V[i]].push_back(U[i]);
	}
	const auto bfs = [&](vector<int> set, int type) {
		vector<int> deg(N);
		for (int i = 0; i < M; ++i) {
			int u = U[i], v = V[i];
			if (alive[u] && alive[v]) {
				deg[u] += 1;
			}
		}
		vector<char> reach(N);
		std::queue<int> que;
		for (const int u : set) {
			reach[u] = true;
			que.push(u);
		}
		while (!que.empty()) {
			const int u = que.front();
			que.pop();
			for (const int v : rG[u]) {
				if (!alive[v] || reach[v]) continue;
				if (A[v] == type) {
					reach[v] = true;
					que.push(v);
				} else if (--deg[v] == 0) {
					reach[v] = true;
					que.push(v);
				}
			}
		}
		return reach;
	};
	while (std::any_of(alive.begin(), alive.end(), [](bool b) { return b; })) {
		vector<int> s;
		for (int i = 0; i < N; ++i) {
			if (alive[i] && R[i]) {
				s.push_back(i);
			}
		}
		auto s2 = bfs(std::move(s), 1);
		vector<int> t;
		for (int i = 0; i < N; ++i) {
			if (alive[i] && !s2[i]) {
				t.push_back(i);
			}
		}
		if (t.empty()) {
			for (int i = 0; i < N; ++i) {
				if (alive[i]) {
					ans[i] = 1;
					alive[i] = false;
				}
			}
			break;
		}
		auto t2 = bfs(std::move(t), 0);
		for (int i = 0; i < N; ++i) {
			if (t2[i]) {
				alive[i] = false;
			}
		}
	}
	return ans;
}

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

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