oj.uz

Submission #786579

# Submission time Handle Problem Language Result Execution time Memory
786579 2023-07-18T09:28:16 Z 이동현(#10029) Paths (RMI21_paths) C++17
56 / 100
 196 ms 71056 KB 
#include <bits/stdc++.h>
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;
    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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21512 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 10 ms 21512 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 9 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 9 ms 21480 KB Output is correct
7 Correct 10 ms 21460 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21512 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 9 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 9 ms 21480 KB Output is correct
7 Correct 10 ms 21460 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Correct 10 ms 21716 KB Output is correct
10 Correct 11 ms 21672 KB Output is correct
11 Correct 11 ms 21692 KB Output is correct
12 Correct 11 ms 21644 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21512 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 9 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 9 ms 21480 KB Output is correct
7 Correct 10 ms 21460 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Correct 10 ms 21716 KB Output is correct
10 Correct 11 ms 21672 KB Output is correct
11 Correct 11 ms 21692 KB Output is correct
12 Correct 11 ms 21644 KB Output is correct
13 Correct 13 ms 21852 KB Output is correct
14 Correct 12 ms 21844 KB Output is correct
15 Correct 13 ms 21768 KB Output is correct
16 Correct 13 ms 21844 KB Output is correct
17 Correct 13 ms 21716 KB Output is correct
18 Correct 12 ms 21716 KB Output is correct
19 Correct 13 ms 21764 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 40460 KB Output is correct
2 Runtime error 104 ms 71056 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 10 ms 21512 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 9 ms 21460 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 9 ms 21480 KB Output is correct
7 Correct 10 ms 21460 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Correct 10 ms 21716 KB Output is correct
10 Correct 11 ms 21672 KB Output is correct
11 Correct 11 ms 21692 KB Output is correct
12 Correct 11 ms 21644 KB Output is correct
13 Correct 13 ms 21852 KB Output is correct
14 Correct 12 ms 21844 KB Output is correct
15 Correct 13 ms 21768 KB Output is correct
16 Correct 13 ms 21844 KB Output is correct
17 Correct 13 ms 21716 KB Output is correct
18 Correct 12 ms 21716 KB Output is correct
19 Correct 13 ms 21764 KB Output is correct
20 Correct 196 ms 40460 KB Output is correct
21 Runtime error 104 ms 71056 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -