제출 #226854

#제출 시각아이디문제언어결과실행 시간메모리
226854MetB경찰관과 강도 (BOI14_coprobber)C++14
0 / 100
23 ms24064 KiB
#include "coprobber.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define N 1000003 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, sm[500]; bool a[500][500]; vector <int> g[N]; 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); } void print (int s) { cout << (s / 2) / n << ' ' << (s / 2) % n << ' ' << s % 2 << endl; } vector <int> get_neighbors (int s) { vector <int> v; int x, y, t; tie (x, y, t) = decouple (s); if (t) { for (int i = 0; i < n; i++) { if (a[x][i] || x == i) { v.push_back (couple (i, y, 0)); } } } else { for (int i = 0; i < n; i++) { if (a[y][i]) { v.push_back (couple (x, i, 1)); } } } return v; } int start (int v, bool A[][500]) { n = v; m = 2 * n * n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) sm[i] += (int) A[i][j]; memcpy (a, A, sizeof (a)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dg[couple (i, j, 0)] = sm[j] + 1; dg[couple (i, j, 1)] = sm[i]; } } fill (d, d + m, 2); 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 (); auto v = get_neighbors (s); if (!d[s]) { for (int to : v) { if (d[to] != 2) continue; d[to] = 1; q.push (to); mv[to] = s; } } else { for (int to : v) { 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...