제출 #810697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810697		Hakiers	Torrent (COI16_torrent)	C++17	0 / 100	676 ms	48696 KiB

torrent

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 3e5 + 7;
const int LOG = 18;
vector<pair<int, int>> G[MAXN];
int wsk[MAXN];
int depth[MAXN];
int dp[MAXN];
bool blocked[MAXN];
int jmp[MAXN][LOG + 1];
int root1, root2;
int res;
int n;

bool cmp(pair<int ,int> a, pair<int, int> b){

    return dp[a.first] > dp[b.first];
}

void dfs(int v, int p, int d = 0){

    depth[v] = d;
    jmp[v][0] = p;
    for(int k = 1; k <= LOG; k++)
        jmp[v][k] = jmp[jmp[v][k-1]][k-1];
    
    for(auto [u, id] : G[v]){
        if(u == p) continue;
        wsk[u] = id;
        dfs(u, v, d+1);
    }
}

void dfs_res(int v, int p){

    dp[v] = 0;
    for(auto [u, id] : G[v]){
        if(u == root1 || u == root2 || blocked[id] || u == p) continue;
        dfs_res(u, v);
    }

    sort(G[v].begin(), G[v].end(), cmp);
    int add = 1;

    for(auto [u, id] : G[v]){
        if(u == root1 || u == root2 || blocked[id] || u == p) continue;
        dp[v] = max(dp[v], dp[u] + add);
        add++;
    }

}

void solve(){

    int v = root1;
    int u = root2;
    for(int k = 0; k <= LOG; k++){
        blocked[wsk[jmp[u][k]]] = true;
        dfs_res(root1, root1);
        dfs_res(root2, root2);
        if(depth[v] < depth[jmp[u][k]] && max(dp[root1], dp[root2]) <= res){
            blocked[wsk[jmp[u][k]]] = false;
            res = max(dp[root1], dp[root2]);
            u = jmp[u][k];
        }
        blocked[wsk[jmp[u][k]]] = false;
    }

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    cin >> root1 >> root2;

    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        G[a].push_back({b, i});
        G[b].push_back({a, i});
    }

    dfs(root1, root1);
    dfs_res(root1, root1);
    dfs_res(root2, root2);

    res = max(dp[root1], dp[root2]);
    /*
    for(int i = 1; i <= n; i++){
        blocked[wsk[i]] = true;

        dfs_res(root1, root1);
        dfs_res(root2, root2);

        res = min(res, max(dp[root1], dp[root2]));

        blocked[wsk[i]] = false;
    }
    */
    solve();

    cout << res << endl;


}

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69