oj.uz

Submission #419625

# Submission time Handle Problem Language Result Execution time Memory
419625 2021-06-07T10:28:15 Z den_tar Cop and Robber (BOI14_coprobber) C++14
16 / 100
 51 ms 1700 KB 
#include "coprobber.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll DIM = 5e2 + 7;
const ll INF = 1e16 + 7;

vector<ll> a[DIM];

ll vis[DIM],de[DIM];

ll n,fl,mc;

ll police;

void dfs(ll v,ll dep){

    vis[v]=1;
    de[v]=dep;

    for(auto to:a[v]){

     if(vis[to]==2)continue;

     if(vis[to]==1){

      vis[to]=2;

      if((de[v]-de[to]+1)>10){
       fl=1;
       return;
      }

     }

    }

    if(fl==1)return;

    for(auto to:a[v]){

     if(vis[to]==2)continue;

     dfs(to,dep+1);

     if(fl==1)return;
    }

    vis[v]=2;
}

void dfs1(ll v,ll d){
     vis[v]=d;
     for(auto to:a[v])
      if(vis[to]==(-1))dfs1(to,d+1);
}

int start(int N, bool A[MAX_N][MAX_N])
{

    n=N;

    for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
      if(A[i][j])a[i].push_back(j);

    dfs(0,1);

    if(fl==1)return -1;

    police=0;

    return police;
}

int nextMove(int R)
{
    for(int i=0;i<n;i++)vis[i]=(-1);

    dfs1(R,0);

    if(vis[police]>2){

     ll cur=(-1),csz=(-1),cs=0,sz,sum;

     for(auto to:a[police]){

      if(vis[to]<vis[police]){

       sum=0;
       sz=a[to].size();

       for(auto to1:a[to])sum+=vis[to1];

       if(cur==(-1) || cs*sz>sum*csz){
        cur=to;
        csz=sz;
        cs=sum;
       }

      }

     }

     police=cur;

    }
    else if(vis[police]==1)police=R;

    return police;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 51 ms 1700 KB Output is correct
5 Correct 14 ms 944 KB Output is correct
6 Correct 48 ms 1536 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 51 ms 1700 KB Output is correct
5 Correct 14 ms 944 KB Output is correct
6 Correct 48 ms 1536 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Incorrect 0 ms 328 KB the situation repeated
9 Halted 0 ms 0 KB -