Submission #1108895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108895		monaxia	Cop and Robber (BOI14_coprobber)	C++17	Compilation error	0 ms	0 KiB

coprobber

// credit: bieoiibe
#include "coprobber.h"
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define mod (long long)(1e9 + 7)
#define eps (long long)(1e-9)
#define vektor vector
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;

const ll Mod = 1e9 + 7;

vector <vector <int>> f(500, vector <int>(500, 10000));
vector <vector <int>> graph(500);

int start(int n, bool a[500][500]){
    for(int i = 0 ; i < n; i ++){
        for(int j = i; j < n; j ++){
            if(a[i][j]) {
                graph[i].pb(j);
                graph[j].pb(i);
            }
        }
    }

    for(int i = 0; i < n; i ++){
        f[i][i] = 0;
        for(auto& x : graph[i]) f[i][x] = f[x][i] = 1;
    }

    for(int j = 0; j < n; j ++){
        for(int i = n - 1; i >= 0; i --){
            for(int k = 0; k < n; k ++){
                if(f[i][j] + f[j][k] < f[i][k]) f[i][k] = f[i][j] + f[j][k];
            }
        }
    }

    // for(int i = 0; i < n; i ++)
    //     for(int j = 0; j < n; j ++) 
    //         cout << i << " " << j << " " << f[i][j] << "\n";
    
    int mn = INT_MAX;

    for(int i = 0; i < n; i ++){
        queue <int> q;
        vector <int> root(n, 0), val(n, -1);

        q.push(i);
        val[i] = 0;

        while(!q.empty()){
            int s = q.front();
            q.pop();

            for(auto& x : graph[s]){
                if(val[x] >= 0 && root[x] != root[root[s]] && val[x] + val[s] >= 2){
                    mn = min(mn, val[x] + val[s] + 1);
                    break;
                }

                if(val[x] == -1){
                    val[x] = val[s] + 1;
                    root[x] = s;
                    q.push(x);
                }
            }
        }
    }

    if(mn >= 5) return -1;
    return 0;
}

int cur = 0, val = 10000;

int nextMove(int pos){
    int temp = cur;
    for(auto& x : graph[temp]){
        if(f[x][pos] < val){
            cur = x;
            val = f[x][pos];
        }
    }

    return cur;
}

void solve(){
    int n;
    cin >> n;

    bool a[500][500];

    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++) cin >> a[i][j];
    }

    cout << start(n, a) << "\n";
    
    int s;
    while(cin >> s){
        cout << nextMove(s) << "\n";
    }
}
 
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
 
    // if(fopen("blank.inp", "r")){
    //     freopen("blank.inp", "r", stdin);
    //     freopen("blank.out", "w", stdout);
    // }
    
    // // cout << 1; return 0;
 
    ll n = 1;
 
    // // cin >> n;

    // while(n) {
    //     solve();
    //     n --;
    //     cout << "\n";
    // }
 
    // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message (stderr)

coprobber.cpp: In function 'int main()':
coprobber.cpp:125:8: warning: unused variable 'n' [-Wunused-variable]
  125 |     ll n = 1;
      |        ^
/usr/bin/ld: /tmp/ccRbFXn2.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3SHwv2.o:coprobber.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status