Submission #1115229

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1115229	2024-11-20T09:00:28 Z	Thunnus	Torrent (COI16_torrent)	C++17	100 / 100	536 ms	41400 KB

torrent

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, a, b, u, v;
    cin >> n >> a >> b;
    a--, b--;
    vvi adj(n);
    for(int i = 0; i < n - 1; i++){
        cin >> u >> v;
        adj[--u].emplace_back(--v);
        adj[v].emplace_back(u);
    }

    vi dp(n), par(n), dep(n);
    vector<pii> edges;
    int chosen = -1;
    auto chosen_edge = [&](int a, int b) -> bool {
        if(chosen == -1) return false;
        return ((a == edges[chosen].fi && b == edges[chosen].se) || (a == edges[chosen].se && b == edges[chosen].fi));
    };

    function<void(int, int)> dfs = [&](int v, int p) -> void {
        vi c;
        par[v] = p;
        for(int &u : adj[v]){
            if(u == p || chosen_edge(v, u)) continue;
            dep[u] = dep[v] + 1;
            c.emplace_back(u);
            dfs(u, v);
        }
        sort(c.begin(), c.end(), [&](const int a, const int b){return dp[a] > dp[b];} );
        for(int i = 0; i < sz(c); i++){
            dp[v] = max(dp[v], dp[c[i]] + i + 1);
        }
        return;
    };

	dfs(0, 0);
    auto find_path = [&]() -> void {
        vector<pii> bedges;
        if(dep[a] < dep[b]) swap(a, b);
        int ta = a, tb = b;
        while(dep[ta] > dep[tb]){
            edges.emplace_back(ta, par[ta]);
            ta = par[ta];
        }
        while(ta != tb){
            edges.emplace_back(ta, par[ta]);
            bedges.emplace_back(tb, par[tb]);
            ta = par[ta];
            tb = par[tb];
        }
        reverse(bedges.begin(), bedges.end());
        for(pii &edge : bedges){
            edges.emplace_back(edge);
        }
        return;
    };
    find_path();
    
    /*cout << "edges:\n";
    for(pii &edge : edges){
		cout << edge.fi << " " << edge.se << "\n";
	}*/
	
	auto print_vec = [&](const vi &vec) -> void {
		for(const int &i : vec){
			cout << i << " ";
		}
		cout << "\n";
	};
	
    auto check = [&](int idx) -> bool {
        chosen = idx;
        fill(dp.begin(), dp.end(), 0);
        //cout << "idx: " << idx << " ";
        dfs(a, a);
        dfs(b, b);
        //cout << "dpa: " << dp[a] << " dpb: " << dp[b] << "\n";
        return (dp[a] < dp[b]);
    };

    auto bs = [&]() -> int {
        int lo = 0, hi = sz(edges) - 1, ret = hi, mid;
        while(hi >= lo){
            mid = lo + (hi - lo) / 2;
            //cout << "lo: " << lo << " mid: " << mid << " hi: " << hi << "\n";
            if(check(mid)){
                lo = mid + 1;
                ret = mid;
            }
            else{
                hi = mid - 1;
            }
        }
        return ret;
    };

    int opt = bs(), ans1 = LLONG_MAX, ans2 = LLONG_MAX;
    check(opt);
	ans1 = max(dp[a], dp[b]);
	//cout << "dp: "; print_vec(dp);
    if(opt + 1 < sz(edges)){
		check(opt + 1);
		ans2 = max(dp[a], dp[b]);
	}
    cout << min(ans1, ans2) << "\n";
    return 0;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:77:7: warning: variable 'print_vec' set but not used [-Wunused-but-set-variable]
   77 |  auto print_vec = [&](const vi &vec) -> void {
      |       ^~~~~~~~~

Subtask #1

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	2 ms	336 KB	Output is correct

Subtask #2

69.0 / 69.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	395 ms	34428 KB	Output is correct
2	Correct	448 ms	37704 KB	Output is correct
3	Correct	507 ms	38472 KB	Output is correct
4	Correct	536 ms	41032 KB	Output is correct
5	Correct	420 ms	31800 KB	Output is correct
6	Correct	351 ms	34108 KB	Output is correct
7	Correct	348 ms	41400 KB	Output is correct