oj.uz

답안 #786505

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
786505 2023-07-18T08:31:30 Z 이동현(#10029) Paths (RMI21_paths) C++17
0 / 100
 125 ms 66500 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

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

    void push(int val){
        st1.insert(val);
        sum += val;
        if((int)st1.size() > sz){
            st2.insert(*st1.begin());
            sum -= *st1.begin();
            st1.erase(st1.begin());
        }
    }

    void erase(int 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, int ndis, vector<int>&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<int> imsi(n);
    getdis(getdis, 0, -1, 0, imsi);

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

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

    pair<int, 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<int>> vc(n);
    vector<vector<int>> child(n);
    vector<int> mx(n);
    vector<int> rtdist(n), maxdep(n);

    auto dodp = [&](auto&&self, int x, int pr, int rt, int 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<int> ans(n);
    maxk heap;
    auto sol = [&](auto&&self, int x, int pr, int add)->void{
        int nans = add + heap.sum + rtdist[x];
        // cout << x << ' ' << add << ' ' << heap.sum << ' ' << rtdist[x] << endl;
        ans[x] = max(ans[x], nans);

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

            if(maxdep[nxt[0]] + nxt[1] == maxdep[x]){
                heap.erase(maxdep[x]);
                heap.push(maxdep[nxt[0]]);
            }

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

            if(maxdep[nxt[0]] + nxt[1] == maxdep[x]){
                heap.erase(maxdep[nxt[0]]);
                heap.push(maxdep[x]);
            }
        }
    };

    for(int rep = 0; rep < 2; ++rep){
        heap = maxk(k - 1);
        int dist = 0, 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);
            }

            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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 125 ms 66500 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -