제출 #168110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
168110		egekabas	Torrent (COI16_torrent)	C++14	0 / 100	43 ms	11640 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 dp[100009];
int calc(int v){
    if(dp[v] != -1)
        return dp[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 dp[v] = ret;
}
int dis[100009];
int maincalc(int v, int curtime, int time){
    if(dis[v] < curtime)
        return 0;
    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 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(ret+curtime < dis[u] && oth[u] == 1 && ret+curtime <= time){
            vis[u] = 1;
            dis[u] = ret+curtime;
            s.insert({ret+curtime, u});
        }
    return 0;
}

int check(int time){
    for(int i = 1; i <= n; ++i){
        vis[i] = 0;
        dis[i] = 1e9;
    }
    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 && oth[i] == 1)
            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);
    }
    for(int i = 1; i <= n; ++i)
        dp[i] = -1;
    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";
}

컴파일 시 표준 에러 (stderr) 메시지

torrent.cpp: In function 'int calc(int)':
torrent.cpp:44: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