oj.uz

Submission #539985

# Submission time Handle Problem Language Result Execution time Memory
539985 2022-03-19T08:41:45 Z doowey Paths (RMI21_paths) C++14
100 / 100
 504 ms 38736 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;
        }
    }
    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.del(i1);
        G.del(i2);
        G.ins(d1);
        G.ins(d2);
    }
}

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:94:9: warning: variable 'a2' set but not used [-Wunused-but-set-variable]
   94 |     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 7 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 7 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10480 KB Output is correct
6 Correct 6 ms 10548 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 7 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10480 KB Output is correct
6 Correct 6 ms 10548 KB Output is correct
7 Correct 7 ms 10452 KB Output is correct
8 Correct 7 ms 10708 KB Output is correct
9 Correct 8 ms 10836 KB Output is correct
10 Correct 7 ms 10708 KB Output is correct
11 Correct 7 ms 10708 KB Output is correct
12 Correct 9 ms 10704 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 7 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10480 KB Output is correct
6 Correct 6 ms 10548 KB Output is correct
7 Correct 7 ms 10452 KB Output is correct
8 Correct 7 ms 10708 KB Output is correct
9 Correct 8 ms 10836 KB Output is correct
10 Correct 7 ms 10708 KB Output is correct
11 Correct 7 ms 10708 KB Output is correct
12 Correct 9 ms 10704 KB Output is correct
13 Correct 10 ms 10964 KB Output is correct
14 Correct 10 ms 11092 KB Output is correct
15 Correct 9 ms 10964 KB Output is correct
16 Correct 10 ms 10964 KB Output is correct
17 Correct 10 ms 10916 KB Output is correct
18 Correct 8 ms 10836 KB Output is correct
19 Correct 10 ms 10964 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 33100 KB Output is correct
2 Correct 415 ms 36716 KB Output is correct
3 Correct 326 ms 33008 KB Output is correct
4 Correct 400 ms 32996 KB Output is correct
5 Correct 417 ms 34504 KB Output is correct
6 Correct 373 ms 32964 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 7 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10480 KB Output is correct
6 Correct 6 ms 10548 KB Output is correct
7 Correct 7 ms 10452 KB Output is correct
8 Correct 7 ms 10708 KB Output is correct
9 Correct 8 ms 10836 KB Output is correct
10 Correct 7 ms 10708 KB Output is correct
11 Correct 7 ms 10708 KB Output is correct
12 Correct 9 ms 10704 KB Output is correct
13 Correct 10 ms 10964 KB Output is correct
14 Correct 10 ms 11092 KB Output is correct
15 Correct 9 ms 10964 KB Output is correct
16 Correct 10 ms 10964 KB Output is correct
17 Correct 10 ms 10916 KB Output is correct
18 Correct 8 ms 10836 KB Output is correct
19 Correct 10 ms 10964 KB Output is correct
20 Correct 403 ms 33100 KB Output is correct
21 Correct 415 ms 36716 KB Output is correct
22 Correct 326 ms 33008 KB Output is correct
23 Correct 400 ms 32996 KB Output is correct
24 Correct 417 ms 34504 KB Output is correct
25 Correct 373 ms 32964 KB Output is correct
26 Correct 504 ms 33572 KB Output is correct
27 Correct 398 ms 36680 KB Output is correct
28 Correct 461 ms 37452 KB Output is correct
29 Correct 348 ms 33256 KB Output is correct
30 Correct 405 ms 33348 KB Output is correct
31 Correct 435 ms 33356 KB Output is correct
32 Correct 429 ms 34984 KB Output is correct
33 Correct 430 ms 33468 KB Output is correct
34 Correct 297 ms 33228 KB Output is correct
35 Correct 374 ms 33424 KB Output is correct
36 Correct 432 ms 38736 KB Output is correct