Submission #886588

#	Time	Username	Problem	Language	Result	Execution time	Memory
886588		Github	Torrent (COI16_torrent)	C++17	69 / 100	234 ms	33148 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;

pair<int, int> edge = {-1, -1};

void dfs(int u, int p, vector<int>& time){
    for (int v: graph[u]){
        if (v != p){
            time[v] = time[u]+1;
            dfs(v, u, time);
        }
    }
}

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

void dfs1(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){
            dfs1(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);
    }
}

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> T1(n), T2(n);
    dfs(a, -1, T1);
    dfs(b, -1, T2);
    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);
    if (edge == make_pair(-1, -1)){
        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;
    }
    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);
    if (it1 != graph[edge.first].end() && it2 != graph[edge.second].end()) {
        graph[edge.first].erase(it1);
        graph[edge.second].erase(it2);
        T1.clear(), T2.clear();
        T1.resize(n), T2.resize(n);
        vector<int> dp1(n), dp2(n);
        dfs1(a, -1, dp1);
        dfs1(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;
    }else{
        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