oj.uz

Submission #786557

# Submission time Handle Problem Language Result Execution time Memory
786557 2023-07-18T09:11:22 Z 이동현(#10029) Paths (RMI21_paths) C++17
56 / 100
 209 ms 71000 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)3e5 + 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){
    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){
    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;
    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});
    }

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

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

    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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21460 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21460 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 10 ms 21460 KB Output is correct
4 Correct 12 ms 21460 KB Output is correct
5 Correct 11 ms 21472 KB Output is correct
6 Correct 10 ms 21488 KB Output is correct
7 Correct 10 ms 21480 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21460 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 10 ms 21460 KB Output is correct
4 Correct 12 ms 21460 KB Output is correct
5 Correct 11 ms 21472 KB Output is correct
6 Correct 10 ms 21488 KB Output is correct
7 Correct 10 ms 21480 KB Output is correct
8 Correct 14 ms 21716 KB Output is correct
9 Correct 11 ms 21656 KB Output is correct
10 Correct 14 ms 21652 KB Output is correct
11 Correct 12 ms 21588 KB Output is correct
12 Correct 12 ms 21588 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21460 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 10 ms 21460 KB Output is correct
4 Correct 12 ms 21460 KB Output is correct
5 Correct 11 ms 21472 KB Output is correct
6 Correct 10 ms 21488 KB Output is correct
7 Correct 10 ms 21480 KB Output is correct
8 Correct 14 ms 21716 KB Output is correct
9 Correct 11 ms 21656 KB Output is correct
10 Correct 14 ms 21652 KB Output is correct
11 Correct 12 ms 21588 KB Output is correct
12 Correct 12 ms 21588 KB Output is correct
13 Correct 14 ms 21844 KB Output is correct
14 Correct 13 ms 21888 KB Output is correct
15 Correct 13 ms 21772 KB Output is correct
16 Correct 14 ms 21860 KB Output is correct
17 Correct 14 ms 21784 KB Output is correct
18 Correct 13 ms 21716 KB Output is correct
19 Correct 14 ms 21888 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 40476 KB Output is correct
2 Runtime error 88 ms 71000 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21460 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 10 ms 21460 KB Output is correct
4 Correct 12 ms 21460 KB Output is correct
5 Correct 11 ms 21472 KB Output is correct
6 Correct 10 ms 21488 KB Output is correct
7 Correct 10 ms 21480 KB Output is correct
8 Correct 14 ms 21716 KB Output is correct
9 Correct 11 ms 21656 KB Output is correct
10 Correct 14 ms 21652 KB Output is correct
11 Correct 12 ms 21588 KB Output is correct
12 Correct 12 ms 21588 KB Output is correct
13 Correct 14 ms 21844 KB Output is correct
14 Correct 13 ms 21888 KB Output is correct
15 Correct 13 ms 21772 KB Output is correct
16 Correct 14 ms 21860 KB Output is correct
17 Correct 14 ms 21784 KB Output is correct
18 Correct 13 ms 21716 KB Output is correct
19 Correct 14 ms 21888 KB Output is correct
20 Correct 209 ms 40476 KB Output is correct
21 Runtime error 88 ms 71000 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -