Submission #883892

#	Time	Username	Problem	Language	Result	Execution time	Memory
883892		Github	Torrent (COI16_torrent)	C++14	69 / 100	279 ms	38652 KiB

torrent

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <climits>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long

vector<vector<int>> graph;

void dfs(int u, int p, vector<int>& dp){
    if (graph[u].size() == 1){
        dp[u] = 0;
        return;
    }
    vector<pair<int, int>> child;
    for (int v: graph[u]){
        if (v != p){
            dfs(v, u, dp);
            child.push_back({dp[v], v});
        }
    }
    sort(child.begin(), child.end(), greater<pair<int, int>>());
    int sz = child.size();
    for (int i = 0; i < sz; i++){
        dp[u] = max(dp[child[i].second]+i+1, dp[u]);
    }
}

void dfs2(int u, int p, vector<int>& time, vector<int>& dp){
    vector<pair<int, int>> child;
    for (int v: graph[u]){
        if (v != p){
            child.push_back({dp[v], v});
        }
    }
    sort(child.begin(), child.end(), greater<pair<int, int>>());
    int sz = child.size();
    for (int i = 0; i < sz; i++){
        time[child[i].second] = time[u]+i+1;
        dfs2(child[i].second, u, time, dp);
    }
}

pair<int, int> edge;

void dfs3(int u, int p, vector<int>& comp){
    for (int v: graph[u]){
        if (v != p){
            if (comp[u] != comp[v]){
                edge = {u, v};
                return;
            }
            dfs3(v, u, comp);
        }
    }
}

int main(){
    int n, a, b; cin >> n >> a >> b;
    a--, b--;
    graph.resize(n);
    for (int i = 0; i < n-1; i++){
        int u, v; cin >> u >> v; u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> dp1(n), dp2(n);
    dfs(a, -1, dp1);
    dfs(b, -1, dp2);
    vector<int> T1(n), T2(n);
    dfs2(a, -1, T1, dp1);
    dfs2(b, -1, T2, dp2);
    vector<int> comp(n);
    for (int i = 0; i < n; i++){
        if (T1[i] < T2[i]){
            comp[i] = 1;
        }else{
            comp[i] = 2;
        }
    }
    dfs3(0, -1, comp);
    auto it1 = find(graph[edge.first].begin(), graph[edge.first].end(), edge.second);
    auto it2 = find(graph[edge.second].begin(), graph[edge.second].end(), edge.first);
    graph[edge.first].erase(it1);
    graph[edge.second].erase(it2);
    dp1.clear(), dp2.clear(), T1.clear(), T2.clear();
    dp1.resize(n); dp2.resize(n), T1.resize(n), T2.resize(n);
    dfs(a, -1, dp1);
    dfs(b, -1, dp2);
    dfs2(a, -1, T1, dp1);
    dfs2(b, -1, T2, dp2);
    int ans = 0;
    for (int i = 0; i < n; i++){
        if (comp[i] == 1) {
            ans = max(ans, T1[i]);
        }else{
            ans = max(ans, T2[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

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