제출 #918348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
918348		asdasdqwer	Torrent (COI16_torrent)	C++14	100 / 100	248 ms	50284 KiB

torrent

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define pii array<int,2>

signed main() {
    int n,a,b;cin>>n>>a>>b;a--;b--;
    vector<vector<int>> g(n);
    for (int i=1;i<n;i++) {
        int c,d;cin>>c>>d;c--;d--;
        g[c].push_back(d);
        g[d].push_back(c);
    }

    vector<vector<int>> child(n);
    vector<int> p(n,-1);
    function<void(int,int)> dfs=[&](int node,int pv) {
        for (int x:g[node]) {
            if (x==pv)continue;
            child[node].push_back(x);
            p[x]=node;
            dfs(x,node);
        }
    };

    dfs(a,-1);

    vector<bool> online(n, false);
    int pt=b;
    while (pt != a) {
        online[pt]=true;
        pt=p[pt];
    }
    online[a]=true;

    vector<int> times(n, 0);

    function<void(int)> dfs2=[&](int node) {
        vector<int> vls;
        for (int x:child[node]) {
            dfs2(x);
            if (!online[x]) {
                vls.push_back(times[x]);
            }
        }
        sort(vls.begin(),vls.end(),greater<int>());

        for (int i=0;i<vls.size();i++) {
            times[node]=max(times[node], vls[i] + i + 1);
        }
    };

    dfs2(a);

    vector<vector<int>> sub;
    pt=-1;
    
    while (pt != a) {
        if (pt == -1) pt=b;
        else pt = p[pt];
        vector<int> tmp;
        for (auto &x:child[pt]) {
            if (!online[x])tmp.push_back(times[x]);
        }
        sort(tmp.begin(),tmp.end(),greater<int>());

        for (int i=0;i<tmp.size();i++) {
            tmp[i] += i + 1;
        }

        // if (tmp.size() == 0) tmp.push_back(0);

        for (int i=tmp.size()-2;i>=0;i--) {
            tmp[i] = max(tmp[i], tmp[i+1]);
        }

        sub.push_back(tmp);
    }

    reverse(sub.begin(),sub.end());

    function<bool(int)> check=[&](int upper) -> bool {
        int s=sub.size();
        vector<int> mn1(s, 1e9), mn2(s,1e9);

        pt = 0;
        int startTime = 0;
        while (pt != s) {
            mn1[pt] = startTime;
            bool found = false;
            for (int i=0;i<sub[pt].size();i++) {
                if (sub[pt][i] + 1 + startTime <= upper) {
                    found = true;
                    startTime += i + 1;
                    pt++;
                    break;
                }
            }

            if (!found) {
                startTime += sub[pt].size() + 1;
                pt++;
            }
        }

        pt = s-1;
        startTime = 0;

        while (pt != -1) {
            mn2[pt] = startTime;
            bool found = false;
            for (int i=0;i<sub[pt].size();i++) {
                if (sub[pt][i] + 1 + startTime <= upper) {
                    found = true;
                    startTime += i + 1;
                    pt--;
                    break;
                }
            }

            if (!found) {
                startTime += sub[pt].size() + 1;
                pt--;
            }
        }

        vector<int> mn(s, 0);
        for (int i=0;i<s;i++) {
            mn[i] = min(mn1[i], mn2[i]) + (sub[i].size() > 0 ? sub[i][0] : 0);
        }

        // for (int x:mn) {
        //     cout<<x<<" ";
        // }
        // cout<<"\n";

        for (int x:mn) {
            if (x > upper) {
                return false;
            }
        }

        return true;
    };

    int l = 0, r = 1e6;
    int ans = -1;
    while (l <= r) {
        int m=l+(r-l)/2;
        if (check(m)) {
            r = m-1;
            ans = m;
        }

        else {
            l = m+1;
        }
    }

    cout<<ans<<"\n";
}

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

torrent.cpp: In lambda function:
torrent.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int i=0;i<vls.size();i++) {
      |                      ~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i=0;i<tmp.size();i++) {
      |                      ~^~~~~~~~~~~
torrent.cpp: In lambda function:
torrent.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for (int i=0;i<sub[pt].size();i++) {
      |                          ~^~~~~~~~~~~~~~~
torrent.cpp:113:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for (int i=0;i<sub[pt].size();i++) {
      |                          ~^~~~~~~~~~~~~~~

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