oj.uz

Submission #1092266

# Submission time Handle Problem Language Result Execution time Memory
1092266 2024-09-23T16:15:28 Z coldbr3w Torrent (COI16_torrent) C++17
100 / 100
 278 ms 31004 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,a,b;
vector<ll>adj[N];
ll dp[N];
vector<ll>order, path;
void dfs_path(ll u, ll par){
    order.pb(u);
    if(u == b) path = order;
    for(auto v : adj[u]){
        if(v == par) continue;
        dfs_path(v, u);
    }
    order.pop_back();
}
void dfs(ll u, ll par, ll tar){
    dp[u] = 1;
    vector<ll>vec;
    for(auto v : adj[u]){
        if(v == par || v == tar) continue;
        dfs(v, u, tar);
        vec.pb(dp[v]);
    }
    sort(all(vec), greater<ll>());
    ll mx = 0;
    for(int i = 0; i < vec.size();i++) mx = max(mx, vec[i] + i);
    dp[u] += mx;
}
ll calc(ll x, ll tar){
    for(int i = 1; i <= n;i++) dp[i] = 0;
    dfs(x, 0, tar);
    return dp[x] - 1;
}
void to_thic_cau(){
    cin >> n >> a >> b;
    for(int i = 1; i <= n - 1;i++){
        ll u,v; cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u);
    }
    dfs_path(a, 0);
    ll l = 0, r = (ll)path.size() - 2, pos = -1;
    while(l <= r){
        ll mid = (l + r) / 2;
        if(calc(a, path[mid + 1]) <= calc(b, path[mid])){
            pos = mid; l = mid + 1;
        }
        else r = mid - 1;
    }
    ll res = inf;
    if(pos != -1) res = max(calc(a, path[pos + 1]), calc(b, path[pos]));
    pos++;
    if(pos + 1 < path.size()) res = min(res, max(calc(a, path[pos + 1]), calc(b, path[pos])));
    cout << res << "\n";
}

signed main()   
{  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

Compilation message

torrent.cpp: In function 'void dfs(long long int, long long int, long long int)':
torrent.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < vec.size();i++) mx = max(mx, vec[i] + i);
      |                    ~~^~~~~~~~~~~~
torrent.cpp: In function 'void to_thic_cau()':
torrent.cpp:64:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     if(pos + 1 < path.size()) res = min(res, max(calc(a, path[pos + 1]), calc(b, path[pos])));
      |        ~~~~~~~~^~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 27220 KB Output is correct
2 Correct 249 ms 28712 KB Output is correct
3 Correct 253 ms 30408 KB Output is correct
4 Correct 278 ms 29544 KB Output is correct
5 Correct 230 ms 26452 KB Output is correct
6 Correct 254 ms 27492 KB Output is correct
7 Correct 244 ms 31004 KB Output is correct