Submission #1119878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119878		PagodePaiva	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	1 ms	336 KiB

coprobber

#include<bits/stdc++.h>
#include "coprobber.h"

using namespace std;

const int MAXN = 510;
vector <int> g[MAXN];
int pai[MAXN];
int h[MAXN];
vector <pair <int, int>> backedges;

void dfs(int v, int p){
    pai[v] = p;
    for(auto x : g[v]){
        if(x == p) continue;
        if(pai[v] != -1){
            backedges.push_back({v, x});
            continue;
        }
        h[x] = h[v]+1;
        dfs(x, v);
    }
    return;
}

int start(int n, bool a[MAX_N][MAX_N]){
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(a[i][j])
                g[i].push_back(j);
        }
    }
    dfs(1, 1);
    int tam = 0;
    for(auto [a, b] : backedges){
        if(h[a] > h[b]) swap(a, b);
        tam = max(tam, h[b]-h[a]+1);
    }
    return (tam >= 5 ? -1 : 0);
}

int nextMove(int R){
    //exit(0);
    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40