oj.uz

Submission #957264

# Submission time Handle Problem Language Result Execution time Memory
957264 2024-04-03T10:55:20 Z ttamx Cop and Robber (BOI14_coprobber) C++17
0 / 100
 61 ms 30876 KB 
#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;
    vis[x][y][t]=2;
    if(t){
        pair<int,int> res(solve(x,y,0),x);
        for(auto v:adj[x])res=max(res,{solve(v,y,0),v});
        return (dp[x][y][t]=res).first;
    }else{
        int res=1;
        for(auto v:adj[y])res=min(res,solve(x,v,1));
        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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Incorrect 61 ms 30876 KB Cop can catch the robber, but start() returned -1
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Cop can catch the robber, but start() returned -1
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Incorrect 1 ms 2392 KB Cop can catch the robber, but start() returned -1
6 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Incorrect 61 ms 30876 KB Cop can catch the robber, but start() returned -1
5 Halted 0 ms 0 KB -