Submission #786570

# Submission time Handle Problem Language Result Execution time Memory
786570 2023-07-18T09:21:59 Z 이동현(#10029) Paths (RMI21_paths) C++17
0 / 100
80 ms 29860 KB
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

const int NS = (int)1e5 + 4;

int sz;
multiset<long long> st1, st2;
vector<pair<int, int>> way[NS];
long long imsi[NS], dis1[NS], dis2[NS];
int oline[NS];
int line[NS], lineN;
long long sum;
vector<long long> vc[NS];
vector<int> child[NS];
long long mx[NS], rtdist[NS], maxdep[NS], ans[NS];

void push(long long val){
    return;
    if(!val) return;
    st1.insert(val);
    sum += val;
    if((int)st1.size() > sz){
        st2.insert(*st1.begin());
        sum -= *st1.begin();
        st1.erase(st1.begin());
    }
}

void erase(long long val){
    return;
    if(!val) return;
    if(!sz || val < *st1.begin()){
        st2.erase(st2.find(val));
        return;
    }
    st1.erase(st1.find(val));
    sum -= val;
    if((int)st1.size() < sz && (int)st2.size()){
        sum += *(--st2.end());
        st1.insert(*(--st2.end()));
        st2.erase(--st2.end());
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    if(n == 1){
        cout << "0\n";
        return 0;
    }
    for(int i = 1; i < n; ++i){
        int x, y, z;
        cin >> x >> y >> z;
        --x, --y;
        way[x].push_back({y, z});
        way[y].push_back({x, z});
    }

    auto getdis = [&](auto&&self, int x, int pr, long long ndis, int tp)->void{
        if(!tp) imsi[x] = ndis;
        else if(tp == 1) dis1[x] = ndis;
        else dis2[x] = ndis;
        for(auto&nxt:way[x]){
            if(nxt.first == pr){
                continue;
            }
            self(self, nxt.first, x, ndis + nxt.second, tp);
        }
    };

    getdis(getdis, 0, -1, 0, 0);

    pair<long long, int> mx1 = {-1, -1};
    for(int i = 0; i < n; ++i){
        mx1 = max(mx1, {imsi[i], i});
    }

    getdis(getdis, mx1.second, -1, 0, 1);

    pair<long long, int> mx2 = {-1, -1};
    for(int i = 0; i < n; ++i){
        mx2 = max(mx2, {dis1[i], i});
    }
    if(mx1.second == mx2.second){
        mx2 = {-1, (mx1.second + 1) % n};
    }

    getdis(getdis, mx2.second, -1, 0, 2);

    int X = mx1.second, Y = mx2.second;

    if(X == Y) while(true){}

    line[lineN++] = X;
    oline[X] = 1;
    int now = X;
    do{
        for(auto&nxt:way[now]){
            if(dis1[nxt.first] + dis2[nxt.first] == dis1[Y] && dis1[now] + nxt.second == dis1[nxt.first]){
                now = nxt.first;
                break;
            }
        }
        line[lineN++] = now;
        oline[now] = 1;
    }while(now != Y);

    auto dodp = [&](auto&&self, int x, int pr, int rt, long long ndis)->void{
        child[rt].push_back(x);
        rtdist[x] = ndis;
        for(auto&nxt:way[x]){
            if(nxt.first == pr || oline[nxt.first]){
                continue;
            }

            self(self, nxt.first, x, rt, ndis + nxt.second);
            maxdep[x] = max(maxdep[x], nxt.second + maxdep[nxt.first]);
            mx[nxt.first] += nxt.second;

            if((int)vc[nxt.first].size() > (int)vc[x].size()){
                swap(vc[x], vc[nxt.first]);
                swap(mx[x], mx[nxt.first]);
            }
            if(!(int)vc[nxt.first].size()){
                continue;
            }
            
            for(auto&i:vc[nxt.first]){
                vc[x].push_back(i);
            }
            if(mx[x] < mx[nxt.first]){
                vc[x].push_back(mx[x]);
                mx[x] = mx[nxt.first];
            }
            else{
                vc[x].push_back(mx[nxt.first]);
            }
        }

        if(!(int)vc[x].size()){
            vc[x] = {0};
        }
    };

    for(int ii = 0; ii < lineN; ++ii){
        int i = line[ii];
        dodp(dodp, i, -1, i, 0);
        vc[i].push_back(mx[i]);
        sort(vc[i].begin(), vc[i].end());
        reverse(vc[i].begin(), vc[i].end());
        while((int)vc[i].size() && vc[i].back() == 0){
            vc[i].pop_back();
        }
    }

    auto sol = [&](auto&&self, int x, int pr, long long add)->void{
        ans[x] = max(ans[x], add + sum + rtdist[x]);

        for(auto&nxt:way[x]){
            if(pr == nxt.first || oline[nxt.first]){
                continue;
            }

            erase(maxdep[nxt.first] + nxt.second);
            push(maxdep[nxt.first]);

            self(self, nxt.first, x, add);

            erase(maxdep[nxt.first]);
            push(maxdep[nxt.first] + nxt.second);
        }
    };

    for(int rep = 0; rep < 2; ++rep){
        sz = k - 1, sum = 0;
        st1.clear(), st2.clear();

        long long dist = 0;
        int pre = X;
        for(int ii = 0; ii < lineN; ++ii){
            int i = line[ii];
            for(auto&nxt:way[i]){
                if(nxt.first == pre){
                    dist += nxt.second;
                    break;
                }
            }
            pre = i;

            for(auto&j:vc[i]){
                push(j);
                // cout << j << ' ';
            }
            // cout << endl;

            sol(sol, i, -1, dist);
        }

        reverse(line, line + lineN);
    }

    if(k >= 2){
        sz = k - 2, sum = 0;
        st1.clear(), st2.clear();

        for(int ii = 0; ii < lineN; ++ii){
            int i = line[ii];
            for(auto&j:vc[i]){
                push(j);
            }
        }
        for(int ii = 0; ii < lineN; ++ii){
            int i = line[ii];
            sol(sol, i, -1, dis1[Y]);
        }
    }

    for(int i = 0; i < n; ++i){
        cout << ans[i] << '\n';
    }

    return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 80 ms 23900 KB Output is correct
2 Runtime error 61 ms 29860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -