Submission #834290

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
834290	2023-08-22T12:39:57 Z	KoD	Toy Train (IOI17_train)	C++17	0 / 100	979 ms	1104 KB

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);
	const auto bfs = [&](vector<int> set, int type) {
		vector<vector<int>> rG(N);
		vector<int> deg(N);
		for (int i = 0; i < M; ++i) {
			int u = U[i], v = V[i];
			if (alive[u] && alive[v]) {
				rG[v].push_back(u);
				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 (A[v] == type) {
					if (!reach[v]) {
						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
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	724 KB	3rd lines differ - on the 22nd token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	224 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Incorrect	1 ms	212 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
5	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	364 ms	1080 KB	Output is correct
2	Correct	734 ms	1080 KB	Output is correct
3	Correct	979 ms	1084 KB	Output is correct
4	Correct	8 ms	976 KB	Output is correct
5	Incorrect	8 ms	980 KB	3rd lines differ - on the 25th token, expected: '1', found: '0'
6	Halted	0 ms	0 KB	-