Submission #1289222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289222		efeg	Paths (RMI21_paths)	C++20	36 / 100	1096 ms	20596 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")


#define ll long long
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
#define endl '\n'

typedef vector<int> vi;
typedef pair<long long,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef tuple<int,int,int> iii;


struct SegTree{
    int n; vii tree; 
    vector<ll> lazy; 
    SegTree(int n) : n(n){
        tree.assign(4 * n + 100,{1e18,-1});
        lazy.assign(4 * n + 100,0); 
    }
    ii merge(ii left,ii right){
        if (left.F > right.F) return left; 
        return right; 
    }

    void push(int node,int s,int e){
        if (lazy[node] == 0) return; 
        tree[node].F += lazy[node]; 
        if (s != e){
            lazy[node*2] += lazy[node]; 
            lazy[node*2+1] += lazy[node]; 
        }
        lazy[node] = 0; 
    }

    void build(int node,int s,int e,vi &order){
        if (s == e) {
            tree[node] = {0,order[s]}; 
            return; 
        }

        int m = (s+e) / 2; 
        build(node*2,s,m,order); 
        build(node*2+1,m+1,e,order); 
        tree[node] = merge(tree[node*2],tree[node*2+1]); 
    }

    ii query(int node,int s,int e,int l,int r){
        push(node,s,e); 
        if (s > e || r < s || e < l) return {-1e18,-1};
        if (l <= s && e <= r) return tree[node]; 
        int m = (s + e) / 2;
        return merge(query(node*2,s,m,l,r),query(node*2+1,m+1,e,l,r)); 
    }

    void update(int node,int s,int e,int l,int r,int delta){
        push(node,s,e); 
        if (s > e || r < s || e < l) return; 
        if (l <= s && e <= r){
            lazy[node] += delta; 
            push(node,s,e); 
            return; 
        }
        int m = (s+e) / 2; 
        update(node*2,s,m,l,r,delta); 
        update(node*2+1,m+1,e,l,r,delta); 
        tree[node] = merge(tree[node*2],tree[node*2+1]); 
    }
}; 

vi tin,tout,order;
vii par; 
vector<vii> adj; 
int n,k,zaman; 

void dfs(int node,int p){
    order.pb(node); 
    tin[node] = zaman; 
    zaman++; 
    for (auto pi : adj[node]){
        int x,w; tie(x,w) = pi; 
        if (x == p) continue; 
        par[x] = {node,w}; 
        dfs(x,node); 
    }
    tout[node] = zaman-1; 
} 

void apply(int node,int p, SegTree &tree){
    for (auto pi : adj[node]){
        int x,w; tie(x,w) = pi; 
        if (x == p) continue; 
        tree.update(1,0,n,tin[x],tout[x],w); 
        apply(x,node,tree); 
    }
}

int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(NULL); cout.tie(NULL);  
    cin >> n >> k; 
    adj.assign(n + 10,vii()); 
    
    for (int i = 0; i < n-1; i++){
        int u,v,w; cin >> u >> v >> w; u--; v--; 
        adj[u].eb(v,w); 
        adj[v].eb(u,w); 
    }
    
    par.assign(n + 10,{-1,-1}); 
    tin.assign(n + 10,-1); 
    tout.assign(n + 10,-1); 
    for (int root = 0; root < n; root++){
        order.clear(); 
        zaman = 0; 
        dfs(root,-1); 
    
        SegTree tree(n + 100); 
        tree.build(1,0,n,order); 
        apply(root,-1,tree); 
        ll ans = 0;

        vi vis(n + 10,0);  
        for (int i = 0; i < k; i++) {
            ii mx = tree.query(1,0,n,0,n);
            ans += mx.F;
            int curr = mx.S; ll w = par[curr].S; 
            while (curr != -1 && !vis[curr]){
                vis[curr] = true; 
                tree.update(1,0,n,tin[curr],tout[curr],-w); 
                curr = par[curr].F; 
                if (curr == root) break; 
                w = par[curr].S;
            }
        }
        cout << ans << endl; 

    }

    return 0; 

}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32