Submission #957263

#	Time	Username	Problem	Language	Result	Execution time	Memory
957263		ttamx	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	70 ms	35396 KiB

coprobber

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

using namespace std;

int n,st;
vector<int> adj[MAX_N];
int vis[MAX_N][MAX_N][2];
pair<int,int> dp[MAX_N][MAX_N][2];

int solve(int x,int y,int t){
    if(x==y)return 1;
    if(vis[x][y][t]==2)return dp[x][y][t].first;
    if(vis[x][y][t]==1)return 0;
    vis[x][y][t]=1;
    if(t){
        pair<int,int> res(solve(x,y,0),x);
        for(auto v:adj[x])res=max(res,{solve(v,y,0),v});
        vis[x][y][t]=2;
        return (dp[x][y][t]=res).first;
    }else{
        int res=1;
        for(auto v:adj[y])res=min(res,solve(x,v,1));
        vis[x][y][t]=2;
        return dp[x][y][t].first=res;
    }
}

int start(int N,bool A[MAX_N][MAX_N]){
    n=N;
    for(int u=0;u<n;u++)for(int v=0;v<n;v++)if(A[u][v])adj[u].emplace_back(v);
    for(int u=0;u<n;u++){
        int res=1;
        for(int v=0;v<n;v++){
            res=min(res,solve(u,v,1));
        }
        if(res)return st=u;
    }
    return -1;
}

int nextMove(int R){
    solve(st,R,1);
    return st=dp[st][R][1].second;
}

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