oj.uz

Submission #883892

# Submission time Handle Problem Language Result Execution time Memory
883892 2023-12-06T10:58:04 Z Github Torrent (COI16_torrent) C++14
69 / 100
 279 ms 38652 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 32824 KB Output is correct
2 Correct 267 ms 36968 KB Output is correct
3 Correct 257 ms 35720 KB Output is correct
4 Correct 261 ms 38100 KB Output is correct
5 Correct 263 ms 31820 KB Output is correct
6 Correct 274 ms 31936 KB Output is correct
7 Correct 256 ms 38652 KB Output is correct