제출 #726126

#제출 시각아이디문제언어결과실행 시간메모리
726126Tigerpants경찰관과 강도 (BOI14_coprobber)C++17
0 / 100
1 ms336 KiB
#include "coprobber.h" #include <iostream> #include <vector> #include <algorithm> #include <numeric> #include <functional> #include <map> #include <set> using namespace std; typedef long long int ll; typedef vector<ll> vll; typedef vector<vll> vvll; typedef vector<vvll> vvvll; typedef pair<ll, ll> pll; typedef vector<pll> vpll; #define rep(i, a, b) for (ll i = a; i < b; i++) #define mp(a, b) make_pair(a, b) #define pb(a) push_back(a) #define sz(a) a.size() vvll g; ll moves[MAX_N][MAX_N]; bool outcome[2][MAX_N][MAX_N]; // [turn][R][C] --> (R', C') ll escapes[MAX_N][MAX_N]; void DFS(bool turn, ll R, ll C, ll src = -1) { // a call to DFS means that this position has just reached a positive outcome if (outcome[turn][R][C]) return; cout << "DFS(" << turn << ", " << R << ", " << C << ", " << src << ")\n"; outcome[turn][R][C] = true; if (turn) { // if cop just moved // mark all adjacent positions as positive DFS(false, R, C, C); for (vll::iterator itr = g[C].begin(); itr != g[C].end(); itr++) { DFS(false, R, *itr, C); } } else { moves[R][C] = src; // if robber just moved // remove one from escapes from all adjacent. if escapes reaches 0, then winning for (vll::iterator itr = g[R].begin(); itr != g[R].end(); itr++) { escapes[*itr][C]--; if (escapes[*itr][C] == 0) { DFS(true, *itr, C); } } } } int start(int N, bool A[MAX_N][MAX_N]) { // initialize g g.resize(N); rep(i, 0, N) { rep(j, 0, N) { if (A[i][j]) { g[i].pb(j); } } } // initialize escapes rep(i, 0, N) { rep(j, 0, N) { escapes[i][j] = sz(g[i]); } } // initialize outcome rep(i, 0, N) { rep(j, 0, N) { outcome[0][i][j] = false; outcome[1][i][j] = false; moves[i][j] = -1; } } // do DFS rep(i, 0, N) { DFS(false, i, i, i); DFS(true, i, i); } // check if all outcomes are positive bool positive = true; rep(i, 0, N) { rep(j, 0, N) { positive &= outcome[0][i][j]; positive &= outcome[1][i][j]; } } return positive - 1; } ll CopPositionNextMove = 0; int nextMove(int R) { return moves[R][CopPositionNextMove]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...