Submission #577417

#TimeUsernameProblemLanguageResultExecution timeMemory
577417Noam527Game (APIO22_game)C++17
60 / 100
4075 ms35488 KiB
#include <bits/stdc++.h> #include "game.h" const int OO = 0; const int OOO = 0; using namespace std; int n, k; vector<vector<int>> g, grev; vector<int> s, e; // s: maximum that reaches us // e: minimum that we can reach // e <= s, except for initial state void init(int nn, int kk) { g.clear(); grev.clear(); s.clear(); e.clear(); n = nn; k = kk; g.resize(n); grev.resize(n); s.resize(n, -1); e.resize(n, n); for (int i = 0; i < k; i++) { s[i] = i; e[i] = i; } } void forward_bfs(int l, int m, int r, int v) { if (!(l <= e[v] && s[v] < m)) return; s[v] = m; queue<int> q; q.push(v); while (q.size()) { int x = q.front(); q.pop(); for (const auto &i : g[x]) { if (!(l <= e[i] && s[i] < m)) continue; s[i] = m; q.push(i); } } } void backward_bfs(int l, int m, int r, int v) { if (!(m < e[v] && s[v] <= r)) return; e[v] = m; queue<int> q; q.push(v); while (q.size()) { int x = q.front(); q.pop(); for (const auto &i : grev[x]) { if (!(m < e[i] && s[i] <= r)) continue; e[i] = m; q.push(i); } } } int add(int layer, int l, int r, int u, int v) { if (OO) { cout << "on layer " << layer << " " << l << " " << r << '\n'; } if (l > r) return 0; int m = (l + r) / 2; if (s[u] >= e[v]) return 1; if (s[u] >= m) forward_bfs(l, m, r, v); if (e[v] <= m) backward_bfs(l, m, r, u); if ((m < s[u] <= r) || (m < e[v] <= r)) { if (add(layer + 1, m + 1, r, u, v)) return 1; } if ((l <= s[u] < m) || (l <= e[v] < m)) { if (add(layer + 1, l, m - 1, u, v)) return 1; } return 0; } void brute_dfs(vector<int> &vis, int v) { if (vis[v]) return; vis[v] = 1; for (const auto &i : g[v]) brute_dfs(vis, i); } int brute() { vector<int> vis(n); for (int i = 0; i < k; i++) { for (auto &x : vis) x = 0; for (const auto &j : g[i]) brute_dfs(vis, j); for (int j = 0; j <= i; j++) if (vis[j]) return 1; } return 0; } int add_teleporter(int u, int v) { if (OO) { cout << "current s: "; for (const auto &i : s) cout << i << " "; cout << '\n'; cout << "current e: "; for (const auto &i : e) cout << i << " "; cout << '\n'; } if (u < k && v < k) { return u >= v; } g[u].push_back(v); grev[v].push_back(u); int x = add(0, 0, k - 1, u, v); if (OOO) { int y = brute(); if (x != y) { cout << "difference! " << x << " " << y << '\n'; return 2; } } return x; }

Compilation message (stderr)

game.cpp: In function 'int add(int, int, int, int, int)':
game.cpp:77:9: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
   77 |  if ((m < s[u] <= r) || (m < e[v] <= r)) {
game.cpp:77:28: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
   77 |  if ((m < s[u] <= r) || (m < e[v] <= r)) {
game.cpp:80:9: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
   80 |  if ((l <= s[u] < m) || (l <= e[v] < m)) {
game.cpp:80:28: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
   80 |  if ((l <= s[u] < m) || (l <= e[v] < m)) {
game.cpp: In function 'int add_teleporter(int, int)':
game.cpp:108:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  108 |   for (const auto &i : s) cout << i << " "; cout << '\n';
      |   ^~~
game.cpp:108:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  108 |   for (const auto &i : s) cout << i << " "; cout << '\n';
      |                                             ^~~~
game.cpp:110:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  110 |   for (const auto &i : e) cout << i << " "; cout << '\n';
      |   ^~~
game.cpp:110:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  110 |   for (const auto &i : e) cout << i << " "; cout << '\n';
      |                                             ^~~~
#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...