oj.uz

Submission #576846

# Submission time Handle Problem Language Result Execution time Memory
576846 2022-06-13T16:16:11 Z dutinmeow Game (APIO22_game) C++17
2 / 100
 1 ms 208 KB 
#include "game.h"

#include <bits/stdc++.h>
using namespace std;

#pragma region y_combinator

#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

#endif

#pragma endregion y_combinator

const int INF = 1e9;

namespace game {
	int N, K;
	vector<int> A, B, C;
	vector<vector<int>> G, H;

	const int LOG_N = 20;
	
	void init(int _N, int _K) {
		N = _N;
		K = _K;
		A.resize(N);
		B.resize(N);
		C.resize(N);
		G.resize(N);
		H.resize(N);
		for (int i = 0; i < K - 1; i++) {
			G[i].push_back(i + 1);
			// H[i + 1].push_back(i);
		}
		for (int i = 0; i < K; i++) {
			A[i] = i;
			B[i] = i;
			C[i] = 0;
		}
		for (int i = K; i < N; i++) {
			A[i] = -INF;
			B[i] = INF;
			C[i] = LOG_N - 1;
		}
	}	

	bool add_teleporter(int s, int t) {
		if (s < K && t < K)
			return t <= s;
		G[s].push_back(t);
		H[t].push_back(s);

		auto dfsa = y_combinator([&](auto dfsa, int u, int b, vector<int> &tem_vec) -> bool {
			if (K < u && B[u] <= A[u])
				return true;
			if (A[u] / (1 << b) == B[u] / (1 << b) && C[u] > b) {
				tem_vec.push_back(u);
				C[u] = b;
			}
			bool ret = false;
			for (int v : G[u]) {
				if (C[v] <= b + 1 && A[v] / (1 << b) < A[u] / (1 << b)) {
					A[v] = A[u];
					if (dfsa(v, b, tem_vec))
						ret = true;
				}
			}
			return ret;
		});

		auto dfsb = y_combinator([&](auto dfsb, int u, int b, vector<int> &tem_vec) -> bool {
			if (K < u && B[u] <= A[u])
				return true;
			if (A[u] / (1 << b) == B[u] / (1 << b) && C[u] > b) {
				tem_vec.push_back(u);
				C[u] = b;
			}
			bool ret = false;
			for (int v : H[u]) {
				if (C[v] <= b + 1 && B[v] / (1 << b) > B[u] / (1 << b)) {
					B[v] = B[u];
					if (dfsb(v, b, tem_vec))
						ret = true;
				}
			}
			return ret;
		});

		vector<int> cur_vec;
		for (int b = LOG_N - 1; b >= 0; b--) {
			if (C[t] <= b && A[t] / (1 << (b - 1)) < A[s] / (1 << (b - 1)))
				cur_vec.push_back(t);
			if (C[s] <= b && B[s] / (1 << (b - 1)) > B[t] / (1 << (b - 1)))
				cur_vec.push_back(s);
			vector<int> tem_vec;
			for (int u : cur_vec) {
				for (int v : H[u])
					A[v] = max(A[v], A[u]);
				for (int v : G[u])
					B[v] = min(B[v], B[u]);
				if (dfsa(u, b - 1, tem_vec) || dfsb(u, b - 1, tem_vec))
					return true;
			}
			cur_vec = tem_vec;
		}
		return false;
	}
}

void init(int N, int K) { game::init(N, K); }

int add_teleporter(int u, int v) { return game::add_teleporter(u, v); }

#define ONLINE_JUDGE

#ifndef ONLINE_JUDGE

namespace {

int read_int() {
	int x;
	if (scanf("%d", &x) != 1) {
		fprintf(stderr, "Error while reading input\n");
		exit(1);
	}
	return x;
}

}  // namespace

int main() {
	int N = read_int();
	int M = read_int();
	int K = read_int();
	std::vector<int> u(M), v(M);
	for (int i = 0; i < M; ++i) {
		u[i] = read_int();
		v[i] = read_int();
	}

	init(N, K);
	int i;
	for (i = 0; i < M; ++i) {
		int answer = add_teleporter(u[i], v[i]);
		if (answer != 0 && answer != 1) {
			i = -1;
			break;
		} else if (answer == 1) {
			break;
		}
	}
	printf("%d\n", i);
	return 0;
}

#endif

Compilation message

game.cpp:6: warning: ignoring '#pragma region y_combinator' [-Wunknown-pragmas]
    6 | #pragma region y_combinator
      | 
game.cpp:31: warning: ignoring '#pragma endregion y_combinator' [-Wunknown-pragmas]
   31 | #pragma endregion y_combinator
      |

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Incorrect 1 ms 208 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Incorrect 1 ms 208 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Incorrect 1 ms 208 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Incorrect 1 ms 208 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -