Submission #884429

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
884429	2023-12-07T10:30:19 Z	Github	Torrent (COI16_torrent)	C++17	69 / 100	183 ms	38720 KB

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 && 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;
}

Subtask #1

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 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	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