Submission #848428

#	Time	Username	Problem	Language	Result	Execution time	Memory
848428		TahirAliyev	Paths (RMI21_paths)	C++17	36 / 100	650 ms	852 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define oo 1e9
#define pii pair<ll, int>

const int MAX = 2002;
int n, k;

pii segTree[4 * MAX];
ll lazy[4 * MAX];

vector<pii> g[MAX];
int timeIn[MAX], timeOut[MAX], rtimeIn[MAX];
ll pathVal[MAX];
bool marked[MAX];
pii par[MAX];

void relax(int node, int l, int r){
    if(lazy[node] == 0) return;
    segTree[node].first += lazy[node];
    if(l != r){
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void build(int node, int l, int r){
    if(l == r){
        segTree[node] = {pathVal[rtimeIn[l]], rtimeIn[l]};
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    segTree[node] = max(segTree[2 * node], segTree[2 * node + 1]);
}

void update(int node, int l, int r, int ul, int ur, ll val){
    relax(node, l, r);
    if(ul > r || l > ur) return;
    if(ul <= l && r <= ur){
        lazy[node] += val;
        relax(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(2 * node, l, mid, ul, ur, val);
    update(2 * node + 1, mid + 1, r, ul, ur, val);
    segTree[node] = max(segTree[2 * node], segTree[2 * node + 1]);
}

int t = 0;
void dfs(int node, int p, ll h){
    timeIn[node] = ++t;
    rtimeIn[t] = node;
    pathVal[node] = h;
    for(pii to : g[node]){
        if(p == to.first) continue;
        par[to.first] = make_pair(node, to.second);
        dfs(to.first, node, h + to.second);
    }
    timeOut[node] = t;
}

int main(){
    cin >> n >> k;
    for(int i = 1; i < n; i++){
        int u, v, a; cin >> u >> v >> a;
        g[u].push_back({v, a});
        g[v].push_back({u, a});
    }
    for(int i = 1; i <= n; i++){
        t = 0;
        memset(lazy, 0, sizeof(lazy));
        memset(marked, 0, sizeof(marked));

        dfs(i, i, 0);
        build(1, 1, n);
        ll ans = 0;
        for(int j = 0; j < k; j++){
            pii m = segTree[1];
            if(m.first == 0) break;
            ans += m.first;
            int a = m.second;
            while(a != i){
                if(marked[a]) break;
                update(1, 1, n, timeIn[a], timeOut[a], -par[a].second);
                marked[a] = true;
                a = par[a].first;
            }
        }
        cout << ans << '\n';
    }
}

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