Submission #1313352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313352		settop	Cop and Robber (BOI14_coprobber)	C++20	100 / 100	240 ms	6388 KiB

coprobber

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

using namespace std;

#define S second
#define F first
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define rfall(i,a,n) for(int i=a;i>=n;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
const int MAXN=5e2+10;

typedef pair<int,int> pii;

int n,cnt[MAXN][MAXN][2],updt[MAXN][MAXN],atual;
vector<int> g[MAXN];
bool z[MAXN][MAXN][2];

void propag(int u,int x,int p){
    if(p==1){
        for(auto j:g[x]){
            if(z[u][j][0]==1) continue;
            cnt[u][j][0]--;
            if(!cnt[u][j][0]){
                z[u][j][0]=1;
                propag(u,j,0);
            }
        }
    }
    else{
        if(!z[u][x][1]){
            z[u][x][1]=1;
            updt[u][x]=u;
            propag(u,x,1);
        }
        for(auto j:g[u]){
            if(z[j][x][1]) continue;
            z[j][x][1]=1;
            updt[j][x]=u;
            propag(j,x,1);
        }
    }
}

int start(int N, bool A[MAX_N][MAX_N]){
    n=N;
    fall(i,0,n-1)
        fall(j,0,n-1) if(A[i][j]) g[i].pb(j);
        
    fall(i,0,n-1){
        fall(j,0,n-1) cnt[i][j][0]=sz(g[j]);
    }

    fall(i,0,n-1){
        if(z[i][i][1]) continue;
        z[i][i][1]=1;
        propag(i,i,1);
    }
    fall(i,0,n-1){
        if(z[i][i][0]) continue;
        z[i][i][0]=1;
        propag(i,i,0);
    }

    fall(i,0,n-1){
        bool ok=1;
        fall(j,0,n-1) ok&=(z[i][j][1]);
        atual=i;
        if(ok) return i;
    }
    return -1;
}

int nextMove(int R){
    if(R==atual) return atual;
    return atual=updt[atual][R];
}

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