oj.uz

Submission #648231

# Submission time Handle Problem Language Result Execution time Memory
648231 2022-10-05T18:56:33 Z Ronin13 Cop and Robber (BOI14_coprobber) C++14
16 / 100
 68 ms 10788 KB 
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

#define MAX_N 500

// modify the following functions
// you can define global variables and functions

int deg[MAX_N][MAX_N][2];
bool used[MAX_N][MAX_N][2];
vector <vector <int> > g(MAX_N);
bool dp[MAX_N][MAX_N][2];
int cur;

struct state{
    int a, b, c;
    state(int a, int b, int c) : a(a), b(b), c(c){
    }
    state(){
        a = b = c = 0;
    }
}wining[MAX_N][MAX_N][2];

int start(int N, bool A[MAX_N][MAX_N]) {
    int n = N;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(A[i][j]) g[i].pb(j);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            deg[i][j][0] = g[i].size() + 1;
            deg[i][j][1] = g[j].size();
        }
    }
    queue <state> q;
    for(int i= 0; i < n; i++){
        dp[i][i][0] = 1;
        dp[i][i][1] = 0;
        q.push({i, i, 0});
        q.push({i, i, 1});
        used[i][i][1] = used[i][i][0] = 1;
    }
    while(!q.empty()){
        state cur = q.front(); q.pop();
        int a = cur.a, b = cur.b, type = cur.c;
        if(type == 0){
            for(int to : g[b]){
                if(used[a][to][1]) continue;
                if(dp[a][b][0])deg[a][to][1]--;
                if(!dp[a][b][0]){
                    dp[a][to][1] = 1;
                    wining[a][to][1] = {a, b, 0};
                    q.push({a, to, 1});
                    used[a][to][1] = true;
                    continue;
                }
                if(!deg[a][to][1])
                    dp[a][to][1] = 0, used[a][to][1] = 1, q.push({a, to, 1});
            }
        }else{
            for(int to : g[a]){
                if(used[to][b][0]) continue;
                if(dp[a][b][1]) deg[to][b][0]--;
                if(!dp[a][b][1]){
                    dp[to][b][0] = 1;
                    q.push({to, b, 0});
                    wining[to][b][0] = {a, b, 1};
                    used[to][b][0] = true;
                    continue;
                }
                if(!deg[to][b][0])
                    dp[to][b][0] = 0, used[to][b][0] = 1, q.push({to, b, 0});
            }
            if(used[a][b][1]) continue;
            if(dp[a][b][1]) deg[a][b][0]--;
            if(!dp[a][b][1]){
                dp[a][b][0] = 1;
                q.push({a, b, 0});
                wining[a][b][0] = {a, b, 1};
                used[a][b][0] = true;
                continue;
            }
            if(!deg[a][b][0])
                dp[a][b][0] = 0, used[a][b][0] = 1, q.push({a, b, 0});
        }

    }
    for(int i = 0; i < n; i++){
        bool ind = true;
        for(int j = 0; j < n; j++)
            ind &= dp[i][j][0];
        if(ind) {
            cur = i;
            return i;
        }
    }
    return -1;
}

int nextMove(int R) {
    cur = wining[cur][R][0].a;
    return cur;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6096 KB Output is correct
2 Correct 3 ms 6224 KB Output is correct
3 Correct 3 ms 6224 KB Output is correct
4 Correct 57 ms 10592 KB Output is correct
5 Correct 20 ms 8272 KB Output is correct
6 Correct 68 ms 10788 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6096 KB Output is correct
2 Correct 3 ms 6224 KB Output is correct
3 Correct 3 ms 6224 KB Output is correct
4 Correct 57 ms 10592 KB Output is correct
5 Correct 20 ms 8272 KB Output is correct
6 Correct 68 ms 10788 KB Output is correct
7 Incorrect 3 ms 6224 KB Cop can catch the robber, but start() returned -1
8 Halted 0 ms 0 KB -