oj.uz

Submission #1032082

# Submission time Handle Problem Language Result Execution time Memory
1032082 2024-07-23T10:59:50 Z TB_ Torrent (COI16_torrent) C++17
100 / 100
 321 ms 105936 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fo(i, n) for(ll i = 0; i<((ll)n);i++)
#define deb(x) cout << #x << " = " << (x) << endl
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define pb push_back
#define rall(x) x.rbegin(), x.rend()
typedef vector<ll> vl;
typedef vector<vl> vvl;

vvl adj(300001), current(300001);
vector<unordered_set<int>> toRoot(300001);
vl score(300001, -1), isPossible;

void dfs(int u, int last = -1){
    for(auto &v : adj[u]){
        if(v == last) continue;
        dfs(v, u);
        toRoot[v].insert(u);
    }
}

ll dfs2(int u, int last = -1){
    if(score[u] != -1) return score[u]; 
    score[u] = 0;
    for(auto &v : adj[u]){
        if(v == last || toRoot[u].count(v)) continue;
        current[u].pb(dfs2(v, u));
    }
    sort(rall(current[u]));
    fo(i, current[u].size()) score[u] = max(score[u], current[u][i]+i+1);
    return score[u];
}

void dfs3(int u, int last, ll left){
    if(left < score[u]) return;
    else if(left == score[u]){
        for(ll i = current[u].size(); i>=0; i--){
            if(current[u][i]+i+1 == score[u]){
                left-=i; // +-1
                break;
            }
        }
    }
    for(auto &v : adj[u]){
        if(v == last || !toRoot[u].count(v)) continue;
        dfs3(v, u, left-1);
    }
    isPossible[u] = 1;
}

bool dfs4(int u, int last = -1){
    bool res = isPossible[u];
    for(auto &v : adj[u]){
        if(v == last || !toRoot[u].count(v)) continue;
        if(!dfs4(v, u)) return 0;
    }
    return res;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n, a, b, from, to;
    cin >> n >> a >> b;
    a--; b--;
    fo(i, n-1){
        cin >> from >> to;
        adj[--from].pb(--to);
        adj[to].pb(from);
    }
    dfs(a);
    dfs(b);
    fo(i, n) dfs2(i);

    ll lo = -1;
    ll hi = n+10;
    while(hi-lo > 1){
        ll mid = (hi+lo) / 2ll;
        isPossible.assign(n, 0);
        dfs3(a, -1, mid);
        dfs3(b, -1, mid);
        if(dfs4(a)) hi = mid;
        else lo = mid;
    }
    cout << hi;

    return 0;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33372 KB Output is correct
2 Correct 12 ms 33432 KB Output is correct
3 Correct 14 ms 33372 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 101200 KB Output is correct
2 Correct 260 ms 103508 KB Output is correct
3 Correct 256 ms 103552 KB Output is correct
4 Correct 321 ms 105296 KB Output is correct
5 Correct 254 ms 100948 KB Output is correct
6 Correct 263 ms 100808 KB Output is correct
7 Correct 270 ms 105936 KB Output is correct