Submission #38548

#	Time	Username	Problem	Language	Result	Execution time	Memory
38548		oTTo_22	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	1551 ms	2048 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
#define se second
#define fi first
using namespace std;

int n,st;
bool g[500][500],viz[500];

int start(int N, bool A[MAX_N][MAX_N])
{
    for (int i=0; i<MAX_N; i++)
        for (int j=0; j<MAX_N; j++)
            g[i][j]=A[i][j];
    n=N;
    return 0;
}

int nextMove(int R)
{
    bool used[n];
    int p[n];
    int dis=0;
    for (int i=0; i<n; i++) {
        p[i]=-1;
        used[i]=0;
    }
    queue < pair < int,int > > q;
    q.push({st,0});
    while (!q.empty()) {
        pair < int,int > v=q.front();
        q.pop();
        used[v.fi]=1;
        if (v.fi==R) {
            dis=v.se;
            break;
        }
        for (int i=0; i<n; i++)
            if (g[v.fi][i] && !used[i] && !viz[i]) {
                p[i]=v.fi;
                q.push({i,v.se+1});
            }
    }
    if (dis==1)
        return R;
    if (dis==2)
        return st;
    int k=R;
    while (p[k]!=st)
        k=p[k];
    viz[k]=1;
    st=k;
    return k;
}

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