oj.uz

Submission #786580

# Submission time Handle Problem Language Result Execution time Memory
786580 2023-07-18T09:28:58 Z 이동현(#10029) Paths (RMI21_paths) C++17
56 / 100
 185 ms 29796 KB 
#include <bits/stdc++.h>
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 || X < 0 || Y < 0 || X >= n || Y >= n) 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 3 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 3 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7456 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 3 ms 7380 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 3 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7456 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 5 ms 7532 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 4 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 3 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7456 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 5 ms 7532 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 4 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 6 ms 7764 KB Output is correct
14 Correct 6 ms 7764 KB Output is correct
15 Correct 5 ms 7664 KB Output is correct
16 Correct 6 ms 7764 KB Output is correct
17 Correct 6 ms 7696 KB Output is correct
18 Correct 5 ms 7636 KB Output is correct
19 Correct 6 ms 7764 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 26308 KB Output is correct
2 Runtime error 66 ms 29796 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 3 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7456 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 5 ms 7532 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 4 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 6 ms 7764 KB Output is correct
14 Correct 6 ms 7764 KB Output is correct
15 Correct 5 ms 7664 KB Output is correct
16 Correct 6 ms 7764 KB Output is correct
17 Correct 6 ms 7696 KB Output is correct
18 Correct 5 ms 7636 KB Output is correct
19 Correct 6 ms 7764 KB Output is correct
20 Correct 185 ms 26308 KB Output is correct
21 Runtime error 66 ms 29796 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -