# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
841842 | 2023-09-02T07:26:08 Z | manizare | Cop and Robber (BOI14_coprobber) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> #include "coprobber.h" using namespace std; #define pb push_back #define ll long long #define ff first #define ss second #define all(s) s.begin(),s.end() int cnt = 0 , dis[500] , par[500] , st[500] , en[500] , cur = 0 , par[500] ; vector <int> G[500] ; void dfs(int v , int p = -1){ st[v] = cnt ; cnt++; for(int i =0 ; i < (int)G[v].size() ; i++){ int u = G[v][i] ; if(u== p)continue ; dis[u] = dis[v] + 1; dfs(u , v) ; } en[v] = cnt ; cnt ++ ; } int start(int n,bool a[500][500]){ for(int i = 0 ; i < n ; i++){ for(int j =0 ; j < n; j++){ if(a[i][j])G[i].pb(j) ; } } dfs(0) ; return 0; } int ch(int v , int u){ if(st[u] >= st[v] && en[v] >= en[u]){ return 1; } return 0 ; } int nextMove(int r){ if(dis[r]-1 == dis[cur])return cur ; for(int i =0 ; i < (int)G[cur].size() ; i++){ int u = G[cur][i] ; if(ch(u, r) && ch(cur , u)){ cur = u; break ; } } return cur ; }