Submission #1155415

#TimeUsernameProblemLanguageResultExecution timeMemory
1155415LudisseyCop and Robber (BOI14_coprobber)C++20
0 / 100
73 ms39492 KiB
#include "coprobber.h" #include <bits/stdc++.h> #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() using namespace std; vector<vector<int>> neigh; vector<vector<vector<int>>> visited; vector<vector<int>> nxt; int pos=0; int dfs(int p, int b, bool t){ if(p==b) return 2; if(visited[p][b][t]>0) return visited[p][b][t]; visited[p][b][t]=1; if(t){ int mx=0; int mxI=0; for (auto np : neigh[p]) { int d=dfs(np, b, false); if(d>mx) {mx=d; mxI=np; } } int d=dfs(p, b, false); if(d>mx) {mx=d; mxI=p; } nxt[p][b]=mxI; return visited[p][b][t]=mx; }else{ int mn=2; for (auto nb : neigh[b]) { int d=dfs(p, nb, true); if(d<mn) {mn=d; } } return visited[p][b][t]=mn; } } int start(int N, bool A[MAX_N][MAX_N]) { visited.resize(N,vector<vector<int>>(N,vector<int>(2,0))); neigh.resize(N); nxt.resize(N,vector<int>(N,0)); for (int i = 0; i < N; i++) { visited[i][i][0]=visited[i][i][1]=2; for (int j = 0; j < N; j++) { if(A[i][j]) { neigh[i].push_back(j); neigh[j].push_back(i); } } } for (int i = 0; i < N; i++) { bool b=true; for (int j = 0; j < N; j++) { if(i==j) continue; int d=dfs(i,j,1); if(d!=2) b=false; } if(b){ pos=i; return i; } } return -1; } int nextMove(int R) { return pos=nxt[pos][R]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...