Submission #576825

#TimeUsernameProblemLanguageResultExecution timeMemory
576825dutinmeowGame (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 namespace game { int N, K; vector<int> A, B; vector<vector<int>> G, H; void init_slow(int _N, int _K) { N = _N; K = _K; A.assign(N, INT_MAX); iota(A.begin(), A.begin() + K, 0); B.assign(N, INT_MIN); iota(B.begin(), B.begin() + K, 0); G.resize(N); H.resize(N); } bool add_teleporter_slow(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 k) -> bool { if (A[u] <= k) return false; A[u] = k; if (A[u] <= B[u]) return true; for (int v : H[u]) if (dfsa(v, k)) return true; return false; }); auto dfsb = y_combinator([&](auto dfsb, int u, int k) -> bool { if (k <= B[u]) return false; B[u] = k; if (A[u] <= B[u]) return true; for (int v : G[u]) if (dfsb(v, k)) return true; return false; }); return dfsa(s, A[t]) || dfsb(t, B[s]); } const int S = 700; vector<int> C, D; void init_mid(int _N, int _K) { N = _N; K = _K; A.assign(N, INT_MAX); B.assign(N, INT_MIN); C.assign(N, INT_MAX); D.assign(N, INT_MIN); for (int i = 0; i < K; i++) { A[i] = i; B[i] = i; C[i] = i / S; D[i] = i / S; } G.resize(N); H.resize(N); } bool add_teleporter_mid(int s, int t) { if (s < K && t < K) return t <= s; G[s].push_back(t); H[t].push_back(s); int p = -1; auto dfsc = y_combinator([&](auto dfsc, int u, int k) -> bool { if (C[u] <= k) return false; C[u] = k; if (C[u] < D[u] || A[u] <= B[u]) return true; else if (C[u] == D[u]) p = u; for (int v : H[u]) if (dfsc(v, k)) return true; return false; }); auto dfsd = y_combinator([&](auto dfsd, int u, int k) -> bool { if (k <= D[u]) return false; D[u] = k; if (C[u] < D[u] || A[u] <= B[u]) return true; else if (C[u] == D[u]) p = u; for (int v : G[u]) if (dfsd(v, k)) return true; return false; }); if (dfsc(s, C[t]) || dfsd(t, D[s])) return true; if (p == -1) return false; int b = C[p]; auto dfsa = y_combinator([&](auto dfsa, int u, int k) -> bool { if (A[u] <= k) return false; A[u] = k; if (A[u] <= B[u]) return true; for (int v : H[u]) if (C[v] == D[v] && C[v] == b && dfsa(v, k)) return true; return false; }); auto dfsb = y_combinator([&](auto dfsb, int u, int k) -> bool { if (k <= B[u]) return false; B[u] = k; if (A[u] <= B[u]) return true; for (int v : G[u]) if (C[v] == D[v] && C[v] == b && dfsb(v, k)) return true; return false; }); for (int i = b * S; i < min((b + 1) * S, K); i++) { for (int v : H[i]) if (C[v] == D[v] && C[v] == b && dfsa(v, A[i])) return true; for (int v : G[i]) if (C[v] == D[v] && C[v] == b && dfsb(v, B[i])); return true; } return false; } const int LOG_N = 20; void init_fast(int _N, int _K) { N = _N; K = _K; A.assign(N, INT_MAX); iota(A.begin(), A.begin() + K, 0); B.assign(N, INT_MIN); iota(B.begin(), B.begin() + K, 0); C.assign(N, LOG_N - 1); fill_n(C.begin(), K, 0); G.resize(N); H.resize(N); } bool add_teleporter_fast(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 && A[u] <= B[u]) return true; if (A[u] / (1 << b) == B[u] / (1 << b) && C[u] > b) { tem_vec.push_back(u); C[u] = b; } 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)) return true; } } return false; }); auto dfsb = y_combinator([&](auto dfsb, int u, int b, vector<int> &tem_vec) -> bool { if (K < u && A[u] <= B[u]) return true; if (A[u] / (1 << b) == B[u] / (1 << b) && C[u] > b) { tem_vec.push_back(u); C[u] = b; } 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)) return true; } } return false; }); 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 = move(tem_vec); } return false; } } bool mid = true; void init(int N, int K) { if (K >= 150000) mid = true; if (mid) game::init_fast(N, K); else game::init_slow(N, K); } int add_teleporter(int u, int v) { if (mid) return game::add_teleporter_fast(u, v); else return game::add_teleporter_slow(u, v); } /* 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; } #undef NDEBUG */

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
      | 
game.cpp: In function 'bool game::add_teleporter_mid(int, int)':
game.cpp:174:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  174 |     if (C[v] == D[v] && C[v] == b && dfsb(v, B[i]));
      |     ^~
game.cpp:175:6: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  175 |      return true;
      |      ^~~~~~
#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...