oj.uz

Submission #834185

# Submission time Handle Problem Language Result Execution time Memory
834185 2023-08-22T11:41:29 Z KoD Toy Train (IOI17_train) C++17
0 / 100
 2000 ms 1236 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<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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 1236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 980 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 Execution timed out 2048 ms 1236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 852 KB Time limit exceeded
2 Halted 0 ms 0 KB -