# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
103519 | pedro_sponchiado | Cop and Robber (BOI14_coprobber) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=510;
vector<int> adj[maxn];
int d[maxn][maxn];
int marc[maxn];
queue<int> pilha;
vector<pair<int, pair<int, int> > > ord_d;
int aux[maxn][maxn];
int seta[maxn][maxn];
int p;
void bfs(int u, int ini){
marc[u]=1;
for(int i=0; i<adj[u].size(); i++){
int v=adj[u][i];
if(marc[v]==0){
d[v][ini]=d[u][ini]+1;
pilha.push(v);
}
}
pilha.pop();
return;
}
int start(int n, bool A[maxn][maxn]){
for(int i=1; i<=n; i++){
for(int k=1; k<=n; k++){
if(A[i][k]) adj[i].push_back(k);
}
}
//calcula as distancias
for(int i=1; i<=n; i++){
for(int k=1; k<=n; k++){
marc[k]=0;
}
pilha.push(i);
while(!pilha.empty())) bfs(pilha.front(), i);
}
//ordena pela distancia
for(int i=1; i<=n; i++){
for(int k=1; k<=n; k++){
ord_d.push_back(make_pair(d[i][k], make_pair(i, k)));
}
}
sort(ord_d.begin(), ord_d.end());
//calcula aux
for(int i=1; i<=n; i++){
for(int k=1; k<=n; k++){
aux[i][k]=maxn;
for(int t=0; t<adj[k].size(); t++){
int l=adj[k][t];
aux[i][k]=min(aux[i][k], d[i][l]);
}
}
}
//calcula pra cada nivel, quais são os caras que diminui distância, e
p=0;
return 0;
}
int nextMove(int r){
p=seta[p][r];
return p;
}