제출 #226807

#제출 시각아이디문제언어결과실행 시간메모리
226807MetB경찰관과 강도 (BOI14_coprobber)C++14
0 / 100
41 ms47480 KiB
#include "coprobber.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define N 2000003 using namespace std; typedef long long ll; typedef unsigned long long ull; const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3; int d[N], dg[N], m, n; int mv[N], gl; vector <int> g[N]; void print (int s) { cout << (s / 2) / n << ' ' << (s / 2) % n << ' ' << s % 2 << endl; } int couple (int x, int y, int t) { return 2 * (x * n + y) + t; } tuple <int, int, int> decouple(int s) { return tuple <int, int, int> ((s / 2) / n, (s / 2) % n, s % 2); } int start (int v, bool A[][500]) { n = v; m = 2 * n * n; for (int i = 0; i < m; i++) { int x, y, t; tie (x, y, t) = decouple (i); d[i] = 2; if (i & 1) { for (int j = 0; j < n; j++) { if (A[y][j]) { dg[i]++, dg[couple (x, j, 0)]++; g[couple (x, j, 0)].push_back (i); } } } else { for (int j = 0; j < n; j++) { if (A[x][j]) { dg[i]++, dg[couple (j, y, 1)]++; g[couple (j, y, 1)].push_back (i); } } } } for (int i = 0; i < m; i += 2) g[i].push_back (i + 1); queue <int> q; for (int i = 0; i < n; i++) { int s = couple (i, i, 0); d[s] = 1, d[s + 1] = 0; q.push (s), q.push (s + 1); } while (!q.empty ()) { int s = q.front (); q.pop (); if (!d[s]) { for (int to : g[s]) { if (d[to] != 2) continue; d[to] = 1; q.push (to); mv[to] = s; } } else { for (int to : g[s]) { if (d[to] != 2) continue; if (--dg[to] < 1) { d[to] = 0; q.push (to); } } } } for (int i = 0; i < n; i++) { int ok = 1; for (int j = 0; j < n; j++) { if (d[couple (i, j, 0)] != 1) { ok = 0; break; } } if (ok) return gl = i; } return -1; } int nextMove (int x) { int s = couple (gl, x, 0); s = mv[s]; gl = (s / 2) / n; return gl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...