Submission #810844

#	Time	Username	Problem	Language	Result	Execution time	Memory
810844		Hakiers	Torrent (COI16_torrent)	C++17	100 / 100	370 ms	32908 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];
vector<int> edges;
int wsk[MAXN];
int depth[MAXN];
int dp[MAXN];
bool blocked[MAXN];
int parent[MAXN];
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;
    parent[v] = p;

    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 BS(){

    int l = 0, r = edges.size(), mid;

    while(l < r){
        mid = (l + r)/2;
        blocked[wsk[edges[mid]]] = true;
        dfs_res(root1, root1);
        dfs_res(root2, root2);
        if(dp[root2] <= dp[root1]) l = mid + 1;
        else r = mid;

        res = min(res, max(dp[root1], dp[root2]));
        blocked[wsk[edges[mid]]] = false;
    }
}

void solve(){

    int v = root1;
    int u = root2;
    
    while(depth[v] < depth[u]){
        edges.push_back(u);
        u = parent[u];
    }

    BS();


}

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: 31 / 31
• Subtask 2: 69 / 69