Submission #256944

#	Time	Username	Problem	Language	Result	Execution time	Memory
256944		MKopchev	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	1 ms	384 KiB

coprobber

#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=500;

void force_win(int c,int r);
void force_loss(int c,int r);

int in[nmax][nmax];

int parent[nmax][nmax];

bool is_won[nmax][nmax],is_lost[nmax][nmax];

int n;

void force_win(int c,int r)
{
    if(is_won[c][r])return;
    is_won[c][r]=1;

    for(int r_prv=0;r_prv<n;r_prv++)
    {
        in[c][r_prv]--;

        if(in[c][r_prv]==0)force_loss(c,r_prv);
    }
}

void force_loss(int c,int r)
{
    if(is_lost[c][r])return;
    is_lost[c][r]=1;

    for(int c_prv=0;c_prv<n;c_prv++)
        if(is_won[c_prv][r]==0)
        {
            parent[c_prv][r]=c;

            force_win(c_prv,r);
        }
}

int adj[nmax];

int me;

int start(int N, bool A[nmax][nmax])
{
    n=N;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(A[i][j]==1)adj[i]++;

    for(int c=0;c<n;c++)
        for(int r=0;r<n;r++)
            in[c][r]=adj[r];

    for(int i=0;i<N;i++)
        force_win(i,i);

    for(int i=0;i<N;i++)
        force_loss(i,i);

    for(int c=0;c<N;c++)
    {
        bool win=1;

        for(int r=0;r<N;r++)
            if(is_won[c][r]==0)win=0;

        if(win)
        {
            me=c;
            return c;
        }
    }
    return -1;
}
int nextMove(int r)
{
    me=parent[me][r];
    return me;
}
/*
int main()
{
    int N=4;
    bool A[nmax][nmax]={{0, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}};

    cout<<start(N,A)<<endl;

    cout<<nextMove(2)<<endl;
    cout<<nextMove(0)<<endl;
    return 0;
}
*/

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