Submission #90170

#	Time	Username	Problem	Language	Result	Execution time	Memory
90170		nikolapesic2802	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	1561 ms	7964 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
#define pb push_back
pair<int,int> dp[MAX_N][MAX_N][2];
vector<vector<int> > graf(MAX_N);
int visited[MAX_N][MAX_N][2];
pair<int,int> sol[MAX_N][MAX_N][2];
int calc(int cop,int robber,int move)
{
    if(visited[cop][robber][move]==2)
        return dp[cop][robber][move].first;
    //printf("Racunam %i %i %i\n",cop,robber,move);
    visited[cop][robber][move]=1;
    if(move==0)
    {
        if(visited[cop][robber][1]==0||visited[cop][robber][1]==2)
        {
            int d=calc(cop,robber,1);
            if(d!=-1)
            {
                d++;
                if(dp[cop][robber][move].first==-1||dp[cop][robber][move].first>d)
                    dp[cop][robber][move]=make_pair(d,cop);
            }
        }
        for(auto p:graf[cop])
        {
            if(visited[p][robber][1]==1)
                continue;
            int d=calc(p,robber,1);
            if(d==-2)
                continue;
            d++;
            if(dp[cop][robber][move].first==-1||dp[cop][robber][move].first>d)
                dp[cop][robber][move]=make_pair(d,p);
        }
    }
    else
    {
        for(auto p:graf[robber])
        {
            if(visited[cop][p][0]==1)
            {
                dp[cop][robber][move]=make_pair(-2,-1);
                break;
            }
            int d=calc(cop,p,0);
            if(d==-2)
            {
                dp[cop][robber][move]=make_pair(-2,-1);
                break;
            }
            d++;
            if(dp[cop][robber][move].first==-1||dp[cop][robber][move].first<d)
                dp[cop][robber][move]=make_pair(d,p);
        }
    }
    if(dp[cop][robber][move].first==-1)
    {
        dp[cop][robber][move]=make_pair(-2,-1);
    }
    visited[cop][robber][move]=2;
    //printf("Za %i %i %i vracam %i %i\n",cop,robber,move,dp[cop][robber][move].first,dp[cop][robber][move].second);
    return dp[cop][robber][move].first;
}
int pozicija;
int start(int N, bool A[MAX_N][MAX_N])
{
    for(int i=0;i<MAX_N;i++)
        for(int j=0;j<MAX_N;j++)
            for(int k=0;k<2;k++)
                if(i==j)
                    dp[i][j][k]={0,-1},visited[i][j][k]=2;
                else
                    dp[i][j][k]={-1,-1},visited[i][j][k]=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(A[i][j])
                graf[i].pb(j);
    int minn=INT_MAX,pos=-1;
    for(int i=0;i<N;i++)
    {
        int maxx=0;
        for(int j=0;j<N;j++)
        {
            for(int i=0;i<MAX_N;i++)
                for(int j=0;j<MAX_N;j++)
                    for(int k=0;k<2;k++)
                        if(i==j)
                            dp[i][j][k]={0,-1},visited[i][j][k]=2;
                        else
                            dp[i][j][k]={-1,-1},visited[i][j][k]=0;
            int d=calc(i,j,0);
            sol[i][j][0]=dp[i][j][0];
            if(d==-2)
                maxx=-2;
            if(maxx!=-2)
                maxx=max(maxx,d);
        }
        if(maxx!=-2)
        {
            if(maxx<minn)
            {
                maxx=minn;
                pos=i;
            }
        }
    }
    pozicija=pos;
    return pos;
}

int nextMove(int R)
{
    calc(pozicija,R,0);
    return pozicija=sol[pozicija][R][0].second;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40