제출 #168111

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
168111		egekabas	Torrent (COI16_torrent)	C++14	0 / 100	44 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, -1);
        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:26: 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