Submission #168109

#	Time	Username	Problem	Language	Result	Execution time	Memory
168109		egekabas	Torrent (COI16_torrent)	C++14	0 / 100	45 ms	13304 KiB

torrent

#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[100009];
int oth[100009];
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;
        }
    }
}
set<pii> s;
int vis[100009];
int othvis[100009];
int calc(int v){
    vector<int> vec;
    vis[v] = 1;
    for(auto u : g[v]){
        if(vis[u] == 1)
            continue;
        vec.pb(calc(u));
    }
    sort(vec.begin(), vec.end(), greater<int>());
    int ret = 0;
    for(int i = 0; i < vec.size(); ++i){
        ret = max(ret, vec[i]+i+1);
    }
    return ret;
}
int maincalc(int v, int curtime, int time){
    if(othvis[v])
        return 0;
    vector<int> vec;
    vis[v] = othvis[v] = 1;
    for(auto u : g[v]){
        if(vis[u] == 1)
            continue;
        vec.pb(calc(u));
    }
    sort(vec.begin(), vec.end(), greater<int>());
    int cur = 2;
    int ret = 1;
    for(auto u : vec){
        if(u + cur + curtime > time){
            ret = cur;
            --cur;
        }
        if(u + cur + curtime > time){
            return 1;
        }
        ++cur;
    }
    for(auto u : g[v])
        if(vis[u] == 0 && oth[u] == 1 && ret+curtime <= time){
            vis[u] = 1;
            s.insert({ret+curtime, u});
        }
    return 0;
}

int check(int time){
    for(int i = 1; i <= n; ++i)
        vis[i] = othvis[i] = 0;
    vis[a] = vis[b] = 1;
    s.insert({0, a});
    s.insert({0, b});
    while(!s.empty()){
        auto it = s.begin();
        if(maincalc((*it).ss, (*it).ff, time))
            return 0;
        s.erase(it);
    }
    for(int i = 1; i <= n; ++i)
        if(vis[i] == 0)
            return 0;
    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[a] = oth[b] = 1;
    dfs1(a, b);
    int l = 0, r = 300009;
    while(l < r){
        int m = (l+r)/2;
        if(check(m))
            r = m;
        else
            l = m+1;
    }
    cout << l << "\n";
}

Compilation message (stderr)

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

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69