# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
395021 | 2021-04-27T15:48:15 Z | Nicholas_Patrick | Cop and Robber (BOI14_coprobber) | C++17 | 1 ms | 328 KB |
#include "coprobber.h" #include <queue> #include <algorithm> using namespace std; int sub; int cop; bool a[MAX_N][MAX_N]; vector<int> adjLis[MAX_N]; //sub2 int sidelength; int start(int n, bool A[MAX_N][MAX_N]){ for(int i=n; i--;)for(int j=n; j--;) a[i][j]=A[i][j]; for(int i=n; i--;)for(int j=n; j--;){ if(a[i][j]) adjLis[i].push_back(j); } sub=0; if(sub==0){ int edge=0; for(int i=n; i--;) edge+=adjLis[i].size(); if(edge==n*2-2) sub=1; } if(sub==0){ int edge=0; for(int i=n; i--;) edge+=adjLis[i].size(); edge>>=1; for(int i=2; i<n; i++){ if(n%i or edge!=n*2-i-n/i) continue; bool can=true; for(int j=n/i; j--;)for(int k=i; k--;){ if(j and not a[j*i+k][(j-1)*i+k]) can=false; if(k and not a[j*i+k][j*i+k-1]) can=false; } if(can){ sidelength=i; sub=2; break; } } } if(sub==0){ if(n<=100) sub=3; } if(sub==0){ sub=4; } if(sub==1){ return cop=0; } if(sub==2){ return cop=0; } if(sub==3){ return -1; // int unlock[MAX_N][MAX_N]; // for(int i=n; i--;)for(int j=n; j--;) // unlock[i][j]=i==j?0:(adjLis[i].size()+1)*adjLis[j].size(); // vector<int> todo; // for(int i=n; i--;) // todo.push_back(i<<9|i); // while(not todo.empty()){ // int x=todo.back(); // todo.pop_back(); // for(int i: adjLis[x>>9])for(int j: adjLis[x&511]){ // } // } // return cop=0; } if(sub==4){ return -1; // } } bool searching(int x, int p, int z){ if(x==z) return true; for(int y: adjLis[x]){ if(y==p) continue; if(searching(y, x, z)) return true; } return false; } int nextMove(int r){ if(sub==1){ for(int ret: adjLis[cop]){ if(searching(ret, cop, r)) return ret; } } if(sub==2){ int cx=cop/sidelength, cy=cop%sidelength; int rx=r/sidelength, ry=cop/sidelength; if(rx-cx>ry-cy){ cx++; }else if(rx-cx<ry-cy){ cy++; } return cx*sidelength+cy; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 284 KB | Output is correct |
2 | Correct | 1 ms | 200 KB | Output is correct |
3 | Incorrect | 1 ms | 328 KB | the situation repeated |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 200 KB | the situation repeated |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 200 KB | Output is correct |
2 | Correct | 0 ms | 200 KB | Output is correct |
3 | Incorrect | 1 ms | 328 KB | the situation repeated |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 284 KB | Output is correct |
2 | Correct | 1 ms | 200 KB | Output is correct |
3 | Incorrect | 1 ms | 328 KB | the situation repeated |
4 | Halted | 0 ms | 0 KB | - |