Submission #959088

#	Time	Username	Problem	Language	Result	Execution time	Memory
959088		berr	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	1 ms	1368 KiB

coprobber

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

#define MAX_N 500

// modify the following functions
// you can define global variables and functions
int pos;
map<array<int, 2>, int> mp;
vector<int> state(250000, -1);

int start(int n, bool a[MAX_N][MAX_N]) {
    vector<array<int, 2>> b;

    vector<int> g[n];

    for(int i=0; i<n; i++){
        for(int l=0; l<n; l++){
            if(a[i][l]){
                g[i].push_back(l);
            }
        }
    }

    vector val(n, vector(n, 0LL));

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            mp[{i, j}]=b.size();
            b.push_back({i, j});
        }
    }
    vector<array<int, 2>> q;

    for(int i=0; i<n; i++){
        state[mp[{i, i}]]=0;
        q.push_back({i, i});
    }
    int pos=0;
    while(pos<q.size()){
        auto [x, y]=q[pos];

        for(auto i: g[x]){
            for(auto l: g[y]){
                val[i][x]++;
                if(val[i][x] == g[y].size()&&i!=l){
                    state[mp[{i, l}]]=x;
                    q.push_back({i, l});
                }
            }
        }

        pos++;
    }

    for(int i=0; i<n; i++){
        int flag=1;
        for(int j=0; j<n; j++){
            if(state[mp[{i, j}]]==-1){
                flag=0;
            }
            
        }
        if(flag){
            pos = i;
            return i+1;
        }
    }

    return -1;
}

int nextMove(int R) {
    pos=state[mp[{pos, R}]];
    return pos+1;
}   
/*
// don't modify the main function
int main() {
    int N;
    cin >> N;
    bool A[MAX_N][MAX_N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }
    int P = start(N,A);
    cout << P << endl;
    int R;
    cin >> R;
    while (true) {
        if (P == R) break;
        P = nextMove(R);
        cout << P << endl;
        if (P == R) break;
        cin >> R;
    }
}
*/

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:41:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while(pos<q.size()){
      |           ~~~^~~~~~~~~
coprobber.cpp:47:30: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |                 if(val[i][x] == g[y].size()&&i!=l){

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