Submission #256956

#	Time	Username	Problem	Language	Result	Execution time	Memory
256956		MKopchev	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	505 ms	4600 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;

bool mem[nmax][nmax];

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

    //cout<<"\tforce_win "<<c<<" "<<r<<endl;

    for(int r_prv=0;r_prv<n;r_prv++)
        if(mem[r][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;

    if(is_won[c][r]==0)
    {
        is_won[c][r]=1;
        parent[c][r]=c;
        force_win(c,r);
    }
    //cout<<"\t\tforce_loss "<<c<<" "<<r<<endl;

    for(int c_prv=0;c_prv<n;c_prv++)
        if(mem[c][c_prv]&&is_won[c_prv][r]==0)
        {
            //cout<<"parent "<<c_prv<<" "<<r<<" is "<<c<<endl;

            parent[c_prv][r]=c;

            force_win(c_prv,r);
        }
}

int adj[nmax];

int me;

int start(int N, bool A[nmax][nmax])
{
    memset(parent,-1,sizeof(parent));

    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            mem[i][j]=A[i][j];

    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;
}
/*
bool A[nmax][nmax];
int main()
{
    int N,M;

    cin>>N>>M;

    for(int i=1;i<=M;i++)
    {
        int u,v;
        cin>>u>>v;
        A[u][v]=1;
        A[v][u]=1;
    }
    cout<<start(N,A)<<endl;

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

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