oj.uz

Submission #834275

# Submission time Handle Problem Language Result Execution time Memory
834275 2023-08-22T12:34:06 Z KoD Toy Train (IOI17_train) C++17
0 / 100
 7 ms 1364 KB 
#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<bool> 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<bool> 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[u] == 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 852 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1148 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1364 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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