oj.uz

Submission #786550

# Submission time Handle Problem Language Result Execution time Memory
786550 2023-07-18T09:03:56 Z 이동현(#10029) Paths (RMI21_paths) C++17
56 / 100
 600 ms 524288 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;
long long sum;

void push(long long val){
    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(!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;
    vector<vector<vector<int>>> way(n);
    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, vector<long long>&vc)->void{
        vc[x] = ndis;
        for(auto&nxt:way[x]){
            if(nxt[0] == pr){
                continue;
            }
            self(self, nxt[0], x, ndis + nxt[1], vc);
        }
    };

    vector<long long> imsi(n);
    getdis(getdis, 0, -1, 0, imsi);

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

    vector<long long> dis1(n), dis2(n);
    getdis(getdis, mx1.second, -1, 0, dis1);

    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, dis2);

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

    vector<int> oline(n);
    vector<int> line = {X};
    oline[X] = 1;
    int now = X;
    do{
        for(auto&nxt:way[now]){
            if(dis1[nxt[0]] + dis2[nxt[0]] == dis1[Y] && dis1[now] + nxt[1] == dis1[nxt[0]]){
                now = nxt[0];
                break;
            }
        }
        line.push_back(now);
        oline[now] = 1;
    }while(now != Y);

    vector<vector<long long>> vc(n);
    vector<vector<int>> child(n);
    vector<long long> mx(n);
    vector<long long> rtdist(n), maxdep(n);

    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[0] == pr || oline[nxt[0]]){
                continue;
            }

            self(self, nxt[0], x, rt, ndis + nxt[1]);
            maxdep[x] = max(maxdep[x], nxt[1] + maxdep[nxt[0]]);
            mx[nxt[0]] += nxt[1];

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

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

    for(auto&i:line){
        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());
    }

    vector<long long> ans(n);
    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[0] || oline[nxt[0]]){
                continue;
            }

            erase(maxdep[nxt[0]] + nxt[1]);
            push(maxdep[nxt[0]]);

            self(self, nxt[0], x, add);

            erase(maxdep[nxt[0]]);
            push(maxdep[nxt[0]] + nxt[1]);
        }
    };

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

        long long dist = 0;
        int pre = X;
        for(auto&i:line){
            for(auto&nxt:way[i]){
                if(nxt[0] == pre){
                    dist += nxt[1];
                    break;
                }
            }
            pre = i;

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

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

        reverse(line.begin(), line.end());
    }

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

        for(auto&i:line){
            for(auto&j:vc[i]){
                push(j);
            }
        }
        for(auto&i:line){
            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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 5 ms 980 KB Output is correct
14 Correct 4 ms 1108 KB Output is correct
15 Correct 4 ms 852 KB Output is correct
16 Correct 5 ms 980 KB Output is correct
17 Correct 5 ms 852 KB Output is correct
18 Correct 3 ms 852 KB Output is correct
19 Correct 5 ms 980 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 38020 KB Output is correct
2 Execution timed out 956 ms 524288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 5 ms 980 KB Output is correct
14 Correct 4 ms 1108 KB Output is correct
15 Correct 4 ms 852 KB Output is correct
16 Correct 5 ms 980 KB Output is correct
17 Correct 5 ms 852 KB Output is correct
18 Correct 3 ms 852 KB Output is correct
19 Correct 5 ms 980 KB Output is correct
20 Correct 328 ms 38020 KB Output is correct
21 Execution timed out 956 ms 524288 KB Time limit exceeded
22 Halted 0 ms 0 KB -