Submission #1130701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130701		mnbvcxz123	Cop and Robber (BOI14_coprobber)	C++20	100 / 100	510 ms	12732 KiB

coprobber

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

constexpr int N=500;

int n;
int dp[2][N][N],cnt[2][N][N],nxt[N][N];
int pos=0;
vector<int>g[N];

int start(int _N, bool _A[N][N]){
    n=_N;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            if(_A[i][j])
                g[i].push_back(j);
    vector<array<int,3>>tmp;
    for(int i=0;i<n;++i){
        dp[1][i][i]=1;
        dp[0][i][i]=1;
        nxt[i][i]=i;
        tmp.push_back({1,i,i});
        tmp.push_back({0,i,i});
    }
    for(int it=0;it<tmp.size();++it){
        auto[t,x,y]=tmp[it];
        if(t==0){
            auto var=g[y];
            for(auto y2:var){
                if(dp[t^1][x][y2])continue;
                ++cnt[t^1][x][y2];
                if(cnt[t^1][x][y2]==(int)g[y2].size()){
                    dp[t^1][x][y2]=1;
                    tmp.push_back({t^1,x,y2});
                }
            }
        }else{
            auto var=g[x];
            var.push_back(x);
            for(auto x2:var){
                if(dp[t^1][x2][y])continue;
                nxt[x2][y]=x;
                dp[t^1][x2][y]=1;
                tmp.push_back({t^1,x2,y});
            }
        }
    }
    for(int i=0;i<n;++i){
        int win=0;
        for(int j=0;j<n;++j)
            if(dp[0][i][j]==1)++win;
        if(win==n)return pos=i;
    }
    return -1;
}

int nextMove(int pos2){
    return pos=nxt[pos][pos2];
}

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