oj.uz

Submission #168117

# Submission time Handle Problem Language Result Execution time Memory
168117 2019-12-11T12:37:09 Z egekabas Torrent (COI16_torrent) C++14
100 / 100
 237 ms 27272 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
int n, a, b;
vector<int> g[300009];
bool oth[300009];

void dfs1(int v, int p){
    if(oth[v]) return;
    for(auto u : g[v]){
        if(u == p)
            continue;
        dfs1(u, v);
        if(oth[u]){
            oth[v] = 1;
            return;
        }
    }
}
int dp[300009];
void calc(int v, int p){
    vector<int> vec;
    for(auto u : g[v]){
        if(u == p)
            continue;
        calc(u, v);
        vec.pb(dp[u]);
    }
    sort(vec.begin(), vec.end(), greater<int>());
    for(int i = 0; i < vec.size(); ++i)
        dp[v] = max(dp[v], i+1+vec[i]);
}
int dis[300009];
priority_queue<pii> pq;

int check(int time){
    for(int i = 1; i <= n; ++i)
        dis[i] = 1e9;
    while(!pq.empty())pq.pop();
    pq.push({0, a});
    pq.push({0, b});
    dis[a] = dis[b] = 0;
    while(!pq.empty()){
        int v = pq.top().ss;
        int curdis = -pq.top().ff;
        pq.pop();
        
        if(curdis > dis[v])
            continue;
        if(curdis > time)
            return 0;
        vector<int> vec;
        for(auto u : g[v]){
            if(oth[u])
                continue;
            vec.pb(dp[u]);
        }
        sort(vec.begin(), vec.end(), greater<int>());
        int cur = 2;
        int ret = 1;
        for(auto u : vec){
            if(curdis + u + cur == time+1){
                ret = cur;
            }
            else if(curdis + u + cur > time)
                return 0;
            ++cur;
        }
        for(auto u : g[v])
            if(oth[u] && dis[u] > curdis+ret){
                dis[u] = curdis+ret;
                pq.push({-dis[u], u});
            }
    }
    return 1;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> a >> b;
    for(int i = 1; i < n; ++i){
        int t1, t2;
        cin >> t1 >> t2;
        g[t1].pb(t2);
        g[t2].pb(t1);
    }
    oth[b] = 1;
    dfs1(a, -1);

    for(int i = 1; i <= n; ++i){
        if(oth[i] == 0) continue;
        for(auto u : g[i]){
            if(oth[u] == 0)
                calc(u, i);
        }
    }
    int l = 0, r = 300009;

    while(l < r){
        int m = l+(r-l)/2;
        if(check(m))
            r = m;
        else
            l = m+1;
    }
    cout << l << "\n";
}

Compilation message

torrent.cpp: In function 'void calc(int, int)':
torrent.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec.size(); ++i)
                    ~~^~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 9 ms 7420 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 23396 KB Output is correct
2 Correct 177 ms 25720 KB Output is correct
3 Correct 223 ms 26584 KB Output is correct
4 Correct 182 ms 26424 KB Output is correct
5 Correct 197 ms 24504 KB Output is correct
6 Correct 204 ms 25000 KB Output is correct
7 Correct 237 ms 27272 KB Output is correct