oj.uz

Submission #417775

# Submission time Handle Problem Language Result Execution time Memory
417775 2021-06-04T09:32:03 Z KULIKOLD Cop and Robber (BOI14_coprobber) C++17
0 / 100
 1 ms 328 KB 
#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int DIM = 507;
int dp[2][DIM][DIM];
bool valid[2][DIM][DIM];
struct node{
    ll turn,a,b;
};
int POS,N;
bool mas[MAX_N][MAX_N];
int depth[2][DIM][DIM];
int start(int N, bool A[MAX_N][MAX_N])
{
    ::N = N;
    queue<node> Q;
    for(int i = 0;i<N;++i){
        dp[0][i][i] = 1;
        dp[1][i][i] = N-1;
        valid[0][i][i] = valid[1][i][i] = 1;
        Q.push({0,i,i});
        Q.push({1,i,i});
    }
    for(int i = 0;i<N;++i)
        for(int j = 0;j<N;++j)
            mas[i][j] = A[i][j];
    for(ll i = 0;i<N;++i){
        for(ll k = 0;k<N;++k)
            for(ll j = 0;j<N;++j){
                if (!A[k][j]){
                    dp[1][i][k]++;
                    if (dp[1][i][k]==N-1){
                        valid[1][i][k] = 1;
                        Q.push({1,i,k});
                    }
                }
            }
    }
    while(!Q.empty()){
        node pos = Q.front();
        Q.pop();
        if (pos.turn==0){
            for(ll a = 0;a<N;++a){
                if (!A[pos.a][a])
                    continue;
                ++dp[1][a][pos.b];
                if (dp[1][a][pos.b]==N-1)
                    Q.push({1,a,pos.b}),valid[1][a][pos.b] = 1,depth[1][a][pos.b] = depth[0][pos.a][pos.b]+1;

            }
        }
        else{
            for(ll b = 0;b<N;++b){
                if (!dp[0][pos.a][b] && A[pos.b][b]){
                    dp[0][pos.a][b] = 1;
                    valid[0][pos.a][b] = 1;
                    Q.push({0,pos.a,b}), valid[0][pos.a][b] = 1, depth[0][pos.a][b] = depth[1][pos.a][pos.b]+1;
                }
            }
        }
    }
    for(ll i = 0;i<N;++i){
        ll flag = 0;
        for(ll j = 0;j<N;++j){
            if (!valid[0][i][j]){
                flag = 1;
                break;
            }
        }
        if (!flag){
            POS = i;
            return i;
        }
    }
    return -1;
}

int nextMove(int R)
{
    int nxt = -1;
    for(ll a = 0;a<N;++a){
        if (valid[1][a][R] && mas[POS][a]){
            if (nxt==-1)
                nxt = a;
            else if (depth[1][nxt][R]>depth[1][a][R])
                nxt = a;
        }
    }
    POS = nxt;
    return nxt;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Incorrect 1 ms 328 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 328 KB the situation repeated
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Incorrect 1 ms 328 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Incorrect 1 ms 328 KB the situation repeated
4 Halted 0 ms 0 KB -