제출 #419625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419625		den_tar	경찰관과 강도 (BOI14_coprobber)	C++14	16 / 100	51 ms	1700 KiB

coprobber

#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 / 16
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40