Submission #732968

#	Time	Username	Problem	Language	Result	Execution time	Memory
732968		n0sk1ll	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	596 ms	24800 KiB

coprobber

#include "coprobber.h"
 
#include <bits/stdc++.h>
 
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
 
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
 
 
 
 
 
 
 
//Note to self: Check for overflow
 
int dje[503][503]; //ako policajac na potezu pobedjuje, gde treba ici?
int zauz[503][503][2]; //<0 ako smo vec izracunali xd
bool dp[503][503][2]; //canwin
//0 - pandur na potezu
//1 - crook na potezu
 
graph g(505);
 
int P;
 
int start(int n, bool A[500][500])
{
    ff(i,0,n) ff(j,i+1,n) if (A[i][j]) g[i].pb(j),g[j].pb(i);

    queue<pair<pii,pii>> bfs;
    ff(i,0,n) bfs.push({{i,i},{0,-1}}),bfs.push({{i,i},{1,-1}});

    //ovo vazi samo kad je lopov na potezu
    ff(i,0,n) ff(j,0,n) zauz[i][j][1]+=(int)g[j].size();
    ff(i,0,n) ff(j,0,n) zauz[i][j][0]=mod;

    while (!bfs.empty())
    {
        int p=bfs.front().xx.xx;
        int l=bfs.front().xx.yy;
        bool ko=bfs.front().yy.xx;
        int okle=bfs.front().yy.yy;
        bfs.pop();

        if (zauz[p][l][ko]<0) continue;

        zauz[p][l][ko]=-1;
        dp[p][l][ko]=true;
        if (ko==0) dje[p][l]=okle;

        if (ko) //crook na trenutnom potezu
        {
            //znaci policajac je bio na proslom
            bfs.push({{p,l},{0,p}});
            for (auto pugde : g[p])
                if (zauz[pugde][l][0]>=0) bfs.push({{pugde,l},{0,p}});

        }
        else //policajac na potezu
        {
            //znaci crook je bio na proslom
            for (auto lugde : g[l])
            {
                zauz[p][lugde][1]--;
                if (zauz[p][lugde][1]==0)
                    if (zauz[p][lugde][1]>=0) bfs.push({{p,lugde},{1,-1}});
            }
        }
    }

    /*cout<<"policajac:"<<endl;
    ff(i,0,n)
    {
        ff(j,0,n) cout<<dp[i][j][0]<<" ";
        cout<<endl;
    } cout<<endl;

    cout<<"lopov:"<<endl;
    ff(i,0,n)
    {
        ff(j,0,n) cout<<dp[i][j][1]<<" ";
        cout<<endl;
    } cout<<endl;

    cout<<"jebem ti kurac:"<<endl;
    ff(i,0,n)
    {
        ff(j,0,n) cout<<dje[i][j]<<" ";
        cout<<endl;
    } cout<<endl;
    cout<<endl;*/

    ff(i,0,n)
    {
        bool moze=true;
        ff(j,0,n) if (!dp[i][j][0]) moze=false;
        if (moze) return P=i,i;
    }

    return -1;
}
 
int nextMove(int R)
{
    return P=dje[P][R],P;
}

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