Submission #918298

#	Time	Username	Problem	Language	Result	Execution time	Memory
918298		asdasdqwer	Torrent (COI16_torrent)	C++14	0 / 100	323 ms	44712 KiB

torrent

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

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

struct tmp {
    int node;
    bool onl;
    int tNeeded;

    bool operator<(const tmp &x) {
        if (tNeeded != x.tNeeded) {
            return tNeeded > x.tNeeded;
        }
        return onl;
    }
};

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<bool> marked(n, false);
    vector<int> ntime(n, 1e9);
    // priority queue: {time, node}
    priority_queue<pii, vector<pii>> pq;
    pq.push({0, a});
    pq.push({0, b});
    ntime[a] = ntime[b] = 0;

    while (!pq.empty()) {
        auto [t, nd]=pq.top();pq.pop();
        if (marked[nd])continue;
        marked[nd] = true;
        ntime[nd] = -t;
        vector<tmp> vls;

        for (auto &x:g[nd]) {
            tmp tt;
            tt.onl = online[x];
            tt.tNeeded = times[x];
            tt.node = x;
            vls.push_back(tt);
        }

        sort(vls.begin(), vls.end());
        int startTime = -t + 1;
        for (int i=0;i<vls.size();i++) {
            if (ntime[vls[i].node] > startTime) {
                ntime[vls[i].node] = startTime;
                pq.push({-startTime, vls[i].node});
                startTime++;
            }
        }
    }

    int mx=0;
    for (int x:ntime) {
        // cout<<x<<" ";
        mx = max(mx, x);
    }
    // cout<<"\n";

    cout<<mx<<"\n";
}

Compilation message (stderr)

torrent.cpp: In lambda function:
torrent.cpp:62: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]
   62 |         for (int i=0;i<vls.size();i++) {
      |                      ~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:78:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |         auto [t, nd]=pq.top();pq.pop();
      |              ^
torrent.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<tmp>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (int i=0;i<vls.size();i++) {
      |                      ~^~~~~~~~~~~

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