oj.uz

Submission #786560

# Submission time Handle Problem Language Result Execution time Memory
786560 2023-07-18T09:16:39 Z 이동현(#10029) Paths (RMI21_paths) C++17
56 / 100
 280 ms 29788 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){
    // 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 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7352 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7396 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7352 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7396 KB Output is correct
8 Correct 6 ms 7508 KB Output is correct
9 Correct 6 ms 7560 KB Output is correct
10 Correct 5 ms 7508 KB Output is correct
11 Correct 5 ms 7508 KB Output is correct
12 Correct 5 ms 7508 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7352 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7396 KB Output is correct
8 Correct 6 ms 7508 KB Output is correct
9 Correct 6 ms 7560 KB Output is correct
10 Correct 5 ms 7508 KB Output is correct
11 Correct 5 ms 7508 KB Output is correct
12 Correct 5 ms 7508 KB Output is correct
13 Correct 9 ms 7740 KB Output is correct
14 Correct 7 ms 7764 KB Output is correct
15 Correct 7 ms 7708 KB Output is correct
16 Correct 8 ms 7728 KB Output is correct
17 Correct 8 ms 7696 KB Output is correct
18 Correct 6 ms 7636 KB Output is correct
19 Correct 10 ms 7780 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 28764 KB Output is correct
2 Runtime error 64 ms 29788 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 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7352 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7396 KB Output is correct
8 Correct 6 ms 7508 KB Output is correct
9 Correct 6 ms 7560 KB Output is correct
10 Correct 5 ms 7508 KB Output is correct
11 Correct 5 ms 7508 KB Output is correct
12 Correct 5 ms 7508 KB Output is correct
13 Correct 9 ms 7740 KB Output is correct
14 Correct 7 ms 7764 KB Output is correct
15 Correct 7 ms 7708 KB Output is correct
16 Correct 8 ms 7728 KB Output is correct
17 Correct 8 ms 7696 KB Output is correct
18 Correct 6 ms 7636 KB Output is correct
19 Correct 10 ms 7780 KB Output is correct
20 Correct 280 ms 28764 KB Output is correct
21 Runtime error 64 ms 29788 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -