oj.uz

Submission #786543

# Submission time Handle Problem Language Result Execution time Memory
786543 2023-07-18T08:59:39 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;

struct maxk{
    int sz;
    multiset<long long> st1, st2;
    long long sum;
    maxk(){}
    maxk(int n){
        sz = n;
        sum = 0;
    }

    void push(long long val){
        // cout << "PUSH " << val << endl;

        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){
        // cout << "ERASE " << val << endl;

        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);
    maxk heap;
    auto sol = [&](auto&&self, int x, int pr, long long add)->void{
        ans[x] = max(ans[x], add + heap.sum + rtdist[x]);

        for(auto&nxt:way[x]){
            if(pr == nxt[0] || oline[nxt[0]]){
                continue;
            }

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

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

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

    for(int rep = 0; rep < 2; ++rep){
        heap = maxk(k - 1);
        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]){
                heap.push(j);
                // cout << j << ' ';
            }
            // cout << endl;

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

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

    if(k >= 2){
        heap = maxk(k - 2);

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
2 Correct 1 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 2 ms 724 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 4 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 0 ms 212 KB Output is correct
2 Correct 1 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 2 ms 724 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 4 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 1080 KB Output is correct
15 Correct 4 ms 852 KB Output is correct
16 Correct 5 ms 980 KB Output is correct
17 Correct 4 ms 852 KB Output is correct
18 Correct 4 ms 844 KB Output is correct
19 Correct 7 ms 1032 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 37964 KB Output is correct
2 Execution timed out 918 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 0 ms 212 KB Output is correct
2 Correct 1 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 2 ms 724 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 4 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 1080 KB Output is correct
15 Correct 4 ms 852 KB Output is correct
16 Correct 5 ms 980 KB Output is correct
17 Correct 4 ms 852 KB Output is correct
18 Correct 4 ms 844 KB Output is correct
19 Correct 7 ms 1032 KB Output is correct
20 Correct 311 ms 37964 KB Output is correct
21 Execution timed out 918 ms 524288 KB Time limit exceeded
22 Halted 0 ms 0 KB -