Submission #1114427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114427		mariaclara	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	227 ms	8192 KiB

coprobber

#include "coprobber.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair 
#define pb push_back
#define fr first
#define sc second

int pai[505][505], cop_pos;
bool vis[505][505][2];
int qtd[505][505];

int start(int N, bool A[MAX_N][MAX_N]) {
    // lugar do policial, lugar do ladrao, de quem é a vez
    vector<vector<int>> edges(N);
    
    queue<trio> fila;

    for(int i = 0; i < N; i++) {
        fila.push({i,i,0});
        fila.push({i,i,1});
        vis[i][i][0] = vis[i][i][1] = 1;
    }

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(A[i][j]) edges[i].pb(j);

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            qtd[i][j] = sz(edges[j]);

    while(!fila.empty()) {
        auto [cop, robber, flag] = fila.front();
        fila.pop();

        if(flag == 0) {
            // é a vez do policial

            for(auto viz : edges[robber]) {
                qtd[cop][viz]--;
                if(qtd[cop][viz] == 0 and !vis[cop][viz][1])
                    fila.push({cop, viz, 1}), vis[cop][viz][1] = 1;
            }
        }
        else {
            // vez do ladrao

            for(auto viz : edges[cop]) {
                if(!vis[viz][robber][0])
                    fila.push({viz, robber, 0}), vis[viz][robber][0] = 1, pai[viz][robber] = cop;
            }

            if(!vis[cop][robber][0])
                fila.push({cop, robber, 0}), vis[cop][robber][0] = 1, pai[cop][robber] = cop;
        }
    }

    for(int i = 0; i < N; i++) {
        bool ok = 1;

        for(int j = 0; j < N; j++) 
            if(!vis[i][j][0]) ok = 0;

        if(ok) return cop_pos = i;
    }

    return -1;
}

int nextMove(int R) {
    return cop_pos = pai[cop_pos][R];
}

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