Submission #1121167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121167		PagodePaiva	Cop and Robber (BOI14_coprobber)	C++17	16 / 100	31 ms	2896 KiB

coprobber

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

using namespace std;

const int MAXN = 510;
vector <int> g[MAXN];
vector <pair <int, int>> backedges;
int pai[MAXN];
int h[MAXN];
int dist[MAXN][MAXN];
int at;

void dfs(int v, int p){
    pai[v] = p;
    for(auto x : g[v]){
        if(x == p) continue;
        if(pai[x] != -1){
            backedges.push_back({x, v});
            continue;
        }
        h[x] = h[v]+1;
        dfs(x, v);
    }
    return;
}
int start(int n, bool a[MAX_N][MAX_N]){
    memset(pai, -1, sizeof pai);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(a[i][j])
                g[i].push_back(j);
        }
    }
    dfs(1, 1);
    for(auto [a, b] : backedges){
        if(h[a] > h[b]) swap(a, b);
        int con = 2;
        while(b != a){
            if(pai[b] == a) break; 
            if(con > 4) break;
            set <int> s;
            int t = b;
            while(t != a){
                s.insert(t);
                t = pai[t];
            }
            s.insert(a);
            int minalt = 1e9, ver = -1;
            for(auto x : g[b]){
                if(s.find(x) == s.end()) continue;
                if(x == a) continue;
                if(minalt > h[x]){
                    ver = x;
                    minalt = min(minalt, h[x]);
                }
            }
            con++;
            b = ver;
        }      
        if(con > 4){
            return 0;
        }
    }
    memset(dist, -1, sizeof dist);
    for(int i = 0;i < n;i++){
        dist[i][i] = 0;
        queue <int> q;
        q.push(i);
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for(auto x : g[v]){
                if(dist[i][x] != -1) continue;
                dist[i][x] = dist[i][v]+1;
                q.push(x);
            }
        }
    }
    return at = 0;
}

int cover[MAXN];

int nextMove(int r){
    //cout << dist[at][r] << ' ';
    if(dist[at][r] == 0){
        return at;
    }
    if(dist[at][r] == 1){
        return at = r;
    }
    if(dist[at][r] == 2){
        return at = at;
    }
    if(dist[at][r] == 3){
        int v = at;
        for(auto x : g[r]){
            for(auto y : g[x]){
                cover[y]++;       
            }
        }
        int ver = g[v][0], mindist = dist[ver][r], mincover = cover[ver];
        //cout << ver << ' ' << mindist << ' ' << mincover << '\n';
        for(auto x : g[v]){
            //cout << dist[x][r] << ' ' << x << '\n';
            if(mindist > dist[x][r]){
                ver = x;
                mindist = dist[x][r];
                mincover = cover[x];
            }
            else if(mindist == dist[x][r] and mincover > cover[x]){
                ver = x;
                mindist = dist[x][r];
                mincover = cover[x];    
            }
            //cout << ver << '\n';
        }
        //cout << ver << ' ';
        //cout << '\n';
        for(auto x : g[r]){
            for(auto y : g[x]){
                cover[y]--;       
            }
        }
        return at = ver;
    }
    int v = at;
    int ver = g[v][0], mindist = dist[ver][r], mincover = cover[ver];
    for(auto x : g[v]){
        if(mindist > dist[x][r]){
            ver = x;
            mindist = dist[x][r];
            mincover = cover[x];
        }
        else if(mindist == dist[x][r] and mincover > cover[x]){
            ver = x;
            mindist = dist[x][r];
            mincover = cover[x];    
        }
    }
    return at = ver;
}

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