Submission #309743

#TimeUsernameProblemLanguageResultExecution timeMemory
309743nicolaalexandraCop and Robber (BOI14_coprobber)C++14
100 / 100
838 ms10712 KiB
#include <bits/stdc++.h> #include "coprobber.h" //#define MAX_N 510 using namespace std; int C,R; struct stare{ int c,r,t; }; stare d[MAX_N*MAX_N*3]; int dp[MAX_N][MAX_N][2],fth[MAX_N][MAX_N],g[MAX_N]; int start (int n, bool a[MAX_N][MAX_N]){ /// stari de pierdere / de castig /// C,R,0/1 - unde se afla politistu si hotu si cine a facut ultima miscare /// C,C,0/1 - stare de castig int p = 1, u = 0; for (int i=0;i<n;++i){ for (int j=0;j<n;j++) g[i] += a[i][j]; d[++u] = {i,i,0}; d[++u] = {i,i,1}; } for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (i != j){ dp[i][j][0] = 1; /// de cate stari castigatoare am nevoie printe vecinii lui i dp[i][j][1] = g[j]; /// am nevoie ca toti vecinii sa fie castigatori ca asta sa fie castigator } while (p <= u){ int c = d[p].c, r = d[p].r, t = d[p].t; /// stare castigatoare ++p; if (!t){ /// trb sa mute hotu for (int i=0;i<n;i++){ if (!a[r][i] || !dp[c][i][1]) continue; dp[c][i][1]--; if (!dp[c][i][1]) /// inseamna ca toate starile vecinilor sunt castigatoare d[++u] = {c,i,1}; } } else { /// politistul se muta sau sta pe loc for (int i=0;i<n;i++){ if ((!a[c][i] && i != c) || !dp[i][r][0]) continue; dp[i][r][0] = 0; d[++u] = {i,r,0}; fth[i][r] = c; /// unde ma duc din starea asta }}} for (int i=0;i<n;i++){ int ok = 1; for (int j=0;j<n;j++) if (dp[i][j][0]){ ok = 0; break; } if (ok) return i; } return -1; } int nextMove (int R){ C = fth[C][R]; return C; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...