oj.uz

Submission #918348

# Submission time Handle Problem Language Result Execution time Memory
918348 2024-01-29T17:14:27 Z asdasdqwer Torrent (COI16_torrent) C++14
100 / 100
 248 ms 50284 KB 
#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";
}

Compilation message

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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 40920 KB Output is correct
2 Correct 218 ms 45408 KB Output is correct
3 Correct 224 ms 48824 KB Output is correct
4 Correct 211 ms 46856 KB Output is correct
5 Correct 205 ms 42360 KB Output is correct
6 Correct 215 ms 43764 KB Output is correct
7 Correct 221 ms 50284 KB Output is correct