Submission #713561

#TimeUsernameProblemLanguageResultExecution timeMemory
713561StickfishCop and Robber (BOI14_coprobber)C++17
100 / 100
909 ms31300 KiB
#include "coprobber.h" #include <iostream> #include <queue> #include <cassert> #include <bitset> #include <vector> using namespace std; bitset<MAX_N> edg[MAX_N]; bitset<MAX_N> redg[MAX_N]; bitset<MAX_N> used[2][MAX_N]; bitset<MAX_N> trused[MAX_N]; int depth[2][MAX_N][MAX_N]; int n; int C; int pR = -1; int start(int N, bool A[MAX_N][MAX_N]) { n = N; int deg[MAX_N]; for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) { edg[i][j] = redg[j][i] = A[i][j]; } for (int i = 0; i < N; ++i) deg[i] = edg[i].count(); for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) { //bad_edg_cnt[0][i][j] = 1; //bad_edg_cnt[1][i][j] = deg[j]; depth[1][i][j] = depth[0][i][j] = 1234567890; } queue<vector<int>> q; for (int i = 0; i < N; ++i) { //bad_edg_cnt[0][i][i] = bad_edg_cnt[1][i][i] = 0; q.push({0, i, i}); q.push({1, i, i}); used[0][i][i] = used[1][i][i] = trused[i][i] = 1; } int timer = 0; while (q.size()) { int t = q.front()[0]; int u = q.front()[1]; int v = q.front()[2]; //cout << t << ' ' << u << ' ' << v << " | "; depth[t][u][v] = timer++; q.pop(); if (t == 0) { for (int nv = redg[v]._Find_first(); nv < n; nv = redg[v]._Find_next(nv)) { if (!used[1][u][nv] && (used[0][u] & edg[nv]) == edg[nv]) { //cout << "(1 " << u << ' ' << nv << ") "; q.push({1, u, nv}); used[1][u][nv] = 1; } } } else { bitset<MAX_N> cedg = redg[u]; cedg[u] = 1; cedg ^= cedg & trused[v]; for (int nu = cedg._Find_first(); nu < n; nu = cedg._Find_next(nu)) { q.push({0, nu, v}); used[0][nu][v] = trused[v][nu] = 1; } } //cout << endl; } for (int u = 0; u < n; ++u) edg[u][u] = 1; for (int u = 0; u < n; ++u) { bool isok = true; for (int v = 0; v < n; ++v) { isok &= used[0][u][v]; //isok &= used[u][v] <= 0; } if (isok) return C = u; } return -1; } int nextMove(int R) { pR = R; for (int nC = edg[C]._Find_first(); nC < n; nC = edg[C]._Find_next(nC)) { if (depth[1][nC][R] < depth[0][C][R]) { return C = nC; } } assert(0); }

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:20:9: warning: variable 'deg' set but not used [-Wunused-but-set-variable]
   20 |     int deg[MAX_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...