답안 #884429

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
884429 2023-12-07T10:30:19 Z Github Torrent (COI16_torrent) C++17
69 / 100
183 ms 38720 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 && p != -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 = {-1, -1};
 
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(){
    speedup
    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);
    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);
        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;
    }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;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 32828 KB Output is correct
2 Correct 170 ms 36972 KB Output is correct
3 Correct 183 ms 35704 KB Output is correct
4 Correct 166 ms 38008 KB Output is correct
5 Correct 170 ms 31764 KB Output is correct
6 Correct 168 ms 32096 KB Output is correct
7 Correct 161 ms 38720 KB Output is correct