Submission #576846

#TimeUsernameProblemLanguageResultExecution timeMemory
576846dutinmeowGame (APIO22_game)C++17
2 / 100
1 ms208 KiB
#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 (stderr)

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
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...