oj.uz

Submission #539834

# Submission time Handle Problem Language Result Execution time Memory
539834 2022-03-19T07:35:54 Z doowey Paths (RMI21_paths) C++14
100 / 100
 515 ms 40788 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
vector<pll> T[N];

int k;
struct magic_set{
    set<pll> ms;
    int cnt = 0;
    pll V = mp(-1,-1);
    ll sum = 0;
    // sum of all elements >= V
    void relocate(){
        auto it = ms.lower_bound(V);
        while(cnt > k){
            sum -= it->fi;
            cnt -- ;
            it ++ ;
            V = *it;
        }
        while(cnt < k){
            if(it == ms.begin()) break;
            it -- ;
            sum += it->fi;
            cnt ++ ;
            V = *it;
        }
        if(k == 1){
            if(!ms.empty()){
                auto it = ms.end();
                it--;
                sum = it->fi;
            }
            else{
                sum = 0;
            }
        }
    }
    void ins(pll X){
        ms.insert(X);
        if(X >= V){
            sum += X.fi;
            cnt++;
        }
        relocate();
    }
    void del(pll X){
        if(X >= V){
            sum -= X.fi;
            cnt -- ;
        }
        ms.erase(X);
        relocate();
    }
};

magic_set Z[N];
pll A[N], B[N];

magic_set G;

void dfs0(int u, int p){
    Z[u].ins(mp(0ll, u));
    for(auto x : T[u]){
        if(x.fi == p) continue;
        dfs0(x.fi, u);

        auto it = Z[x.fi].ms.end();
        it -- ;
        A[x.fi] = *it;
        B[x.fi] = mp(it->fi + x.se, it->se);
        Z[x.fi].del(A[x.fi]);
        Z[x.fi].ins(B[x.fi]);
        if(Z[u].ms.size() < Z[x.fi].ms.size()){
            swap(Z[u], Z[x.fi]);
        }
        for(auto x : Z[x.fi].ms){
            Z[u].ins(x);
        }
        Z[x.fi].ms.clear();
        Z[x.fi].sum = 0;
        Z[x.fi].cnt = 0;
    }
}

ll sol[N];

void reroot(int u, int v, pll go){
    sol[u] = G.sum;
    pll m1 = mp(0, u);
    pll m2 = mp(0, u);
    int a1 = u;
    int a2 = u;
    pll nx;
    for(auto x : T[u]){
        if(x.fi == v) continue;
        if(B[x.fi] > m1){
            m2 = m1;
            a2 = a1;
            m1 = B[x.fi];
            a1 = x.fi;
        }
        else if(B[x.fi] > m2){
            m2 = B[x.fi];
            a2 = x.fi;
        }
    }
    pll d1, i1;
    pll d2, i2;
    for(auto x : T[u]){
        if(x.fi == v) continue;
        d1 = B[x.fi];
        i1 = A[x.fi];
        nx = go;
        if(x.fi != a1){
            nx = max(nx, m1);
        }
        else{
            nx = max(nx, m2);
        }
        d2 = nx;
        i2 = mp(nx.fi + x.se, nx.se);
        G.del(d1);
        G.del(d2);
        G.ins(i1);
        G.ins(i2);
        reroot(x.fi, u, i2);
        G.ins(d1);
        G.ins(d2);
        G.del(i1);
        G.del(i2);
    }
}

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n;
    cin >> n >> k;
    int u, v, w;
    for(int i = 1; i < n; i ++ ){
        cin >> u >> v >> w;
        T[u].push_back(mp(v, w));
        T[v].push_back(mp(u, w));
    }
    dfs0(1, -1);
    G = Z[1];
    reroot(1, -1, mp(-1ll, -1ll));
    for(int i = 1; i <= n; i ++ ){
        cout << sol[i] << "\n";
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void reroot(int, int, pll)':
Main.cpp:104:9: warning: variable 'a2' set but not used [-Wunused-but-set-variable]
  104 |     int a2 = u;
      |         ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 7 ms 10452 KB Output is correct
6 Correct 6 ms 10528 KB Output is correct
7 Correct 7 ms 10452 KB Output is correct
8 Correct 8 ms 10708 KB Output is correct
9 Correct 7 ms 10708 KB Output is correct
10 Correct 8 ms 10708 KB Output is correct
11 Correct 8 ms 10708 KB Output is correct
12 Correct 8 ms 10708 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 7 ms 10452 KB Output is correct
6 Correct 6 ms 10528 KB Output is correct
7 Correct 7 ms 10452 KB Output is correct
8 Correct 8 ms 10708 KB Output is correct
9 Correct 7 ms 10708 KB Output is correct
10 Correct 8 ms 10708 KB Output is correct
11 Correct 8 ms 10708 KB Output is correct
12 Correct 8 ms 10708 KB Output is correct
13 Correct 13 ms 10964 KB Output is correct
14 Correct 11 ms 11108 KB Output is correct
15 Correct 10 ms 10964 KB Output is correct
16 Correct 10 ms 10964 KB Output is correct
17 Correct 11 ms 10964 KB Output is correct
18 Correct 14 ms 10876 KB Output is correct
19 Correct 13 ms 10964 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 33188 KB Output is correct
2 Correct 408 ms 36624 KB Output is correct
3 Correct 370 ms 32988 KB Output is correct
4 Correct 429 ms 32992 KB Output is correct
5 Correct 432 ms 34380 KB Output is correct
6 Correct 454 ms 32900 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 7 ms 10452 KB Output is correct
6 Correct 6 ms 10528 KB Output is correct
7 Correct 7 ms 10452 KB Output is correct
8 Correct 8 ms 10708 KB Output is correct
9 Correct 7 ms 10708 KB Output is correct
10 Correct 8 ms 10708 KB Output is correct
11 Correct 8 ms 10708 KB Output is correct
12 Correct 8 ms 10708 KB Output is correct
13 Correct 13 ms 10964 KB Output is correct
14 Correct 11 ms 11108 KB Output is correct
15 Correct 10 ms 10964 KB Output is correct
16 Correct 10 ms 10964 KB Output is correct
17 Correct 11 ms 10964 KB Output is correct
18 Correct 14 ms 10876 KB Output is correct
19 Correct 13 ms 10964 KB Output is correct
20 Correct 472 ms 33188 KB Output is correct
21 Correct 408 ms 36624 KB Output is correct
22 Correct 370 ms 32988 KB Output is correct
23 Correct 429 ms 32992 KB Output is correct
24 Correct 432 ms 34380 KB Output is correct
25 Correct 454 ms 32900 KB Output is correct
26 Correct 462 ms 35616 KB Output is correct
27 Correct 345 ms 38768 KB Output is correct
28 Correct 458 ms 39536 KB Output is correct
29 Correct 383 ms 35356 KB Output is correct
30 Correct 419 ms 35480 KB Output is correct
31 Correct 503 ms 34908 KB Output is correct
32 Correct 515 ms 37052 KB Output is correct
33 Correct 398 ms 35588 KB Output is correct
34 Correct 294 ms 35380 KB Output is correct
35 Correct 375 ms 35480 KB Output is correct
36 Correct 439 ms 40788 KB Output is correct