Submission #135998

#	Time	Username	Problem	Language	Result	Execution time	Memory
135998		forelax	Cop and Robber (BOI14_coprobber)	C++14	30 / 100	97 ms	6052 KiB

coprobber

#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<bool> > wing(500,vector<bool> (500));
vector<vector<bool> > winb(500,vector<bool> (500));
vector<vector<int> > cntl(500,vector<int> (500));
vector<vector<int> > go(500,vector<int> (500));
vector<vector<bool> > a(500,vector<bool> (500));
vector<vector<int> > edge(500);
int n,cr=0;
int start(int _N,bool A[500][500]){
    n=_N;
    queue<vector<int> > q;
    for(int i = 0 ; i < n ; i ++){
        for(int j = 0 ; j < n ; j ++){
            a[i][j]=A[i][j];
            if(a[i][j]){
                edge[i].push_back(j);
                wing[i][j]=true;
                q.push({0,i,j});
                go[i][j]=j;
            }
        }
    }
    for(int i = 0 ; i < n ; i ++){
        for(int j = 0 ; j < n ; j ++){
            if(i==j)continue;
            cntl[i][j]=edge[j].size();
            if(a[j][i])cntl[i][j]--;
        }
    }
    while(q.size()){
        vector<int> nw=q.front();
        q.pop();
        int x=nw[2];
        int y=nw[1];
        int st=nw[0];
        if(st==0){
            for(int i = 0 ; i < edge[x].size() ; i ++){
                int ne=edge[x][i];
                if(ne==y)continue;
                cntl[y][ne]--;
                if(cntl[y][ne])continue;
                q.push({1,y,ne});
                winb[y][ne]=true;
            }
        }else{
            for(int i = 0 ; i < edge[y].size() ; i ++){
                int ne=edge[y][i];
                if(ne==x)continue;
                if(wing[ne][x])continue;
                go[ne][x]=y;
                wing[ne][x]=true;
                q.push({0,ne,x});
            }
        }
    }
    cr=0;
    return 0;
}
int nextMove(int np){
    cr=go[cr][np];
    return cr;
}/*
int main(){
    int N;
    cin>>N;
    vector<vector<int> > A(N,vector<int> (N));
    for(int i = 0 ; i < N ;i ++){
        for(int j = 0 ; j < N ; j ++){
            cin>>A[i][j];
        }
    }
    int CP=start(N,A),one;
    cin>>one;
    vector<vector<int> > dir(n,vector<int> (n+1));
    for(int i = 0 ; i < N ; i ++)
        for(int j = 0 ; j <= N ; j ++)
            cin>>dir[i][j];
    int BP=dir[CP].back();
    while(CP!=BP){
        cout<<CP<<" "<<BP<<" ";
        BP=dir[CP][BP];
        CP=nextMove(BP);
    }
    cout<<CP<<" "<<BP;
}*/

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:39:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0 ; i < edge[x].size() ; i ++){
                             ~~^~~~~~~~~~~~~~~~
coprobber.cpp:48:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0 ; i < edge[y].size() ; i ++){
                             ~~^~~~~~~~~~~~~~~~

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