Submission #1224619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224619		jordan	Paths (RMI21_paths)	C++20	36 / 100	1095 ms	17476 KiB

Main

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

const int mxN = 1e5+10;
const ll INF = 1e18;

vector<array<ll, 2>> adj[mxN];
int cnt = -1, n, k;
int tin[mxN], tout[mxN];
array<ll, 2> st[mxN*4];
ll l = INF, r = 0, curr_ans = 0;
ll ans[mxN];

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

array<ll, 2> qry(int node, int l, int r, int l1, int r1) {
    if(l1 <= l && r <= r1) return st[node];
    if(l1 > r || r1 < l) return {-1, 0};
    int mid = (l+r)/2;
    return max(qry(node*2, l, mid, l1, r1),
               qry(node*2+1, mid+1, r, l1, r1));
}

void upd(int node, int l, int r, int k, ll x) {
    if(l == r && l == k) {
        st[node][0] += x;
        return ;
    }
    if(l > k || r < k) return ;
    int mid = (l+r)/2;
    upd(node*2, l, mid, k, x);
    upd(node*2+1, mid+1, r, k, x);
    st[node] = max(st[node*2], st[node*2+1]);
}

void dfs(int node, int p) {
    bool leaf = true;
    tin[node] = mxN;
    for(auto [it, w] : adj[node]) { //
        if(it == p) continue;
        dfs(it, node);
        array<ll, 2> now = qry(1, 0, n-1, tin[it], tout[it]);
        upd(1, 0, n-1, now[1], w);
        tin[node] = min(tin[node], tin[it]);
        tout[node] = max(tout[node], tout[it]);
        leaf = false;
    }
    if(leaf) tin[node] = tout[node] = ++cnt;
}

multiset<ll, greater<ll>> vals, dist;

void dfs1(int node, int p) {
    ans[node] = curr_ans;
    for(auto [it, w] : adj[node]) {
        if(it == p) continue;
        array<ll, 2> nxt = qry(1, 0, n-1, tin[it], tout[it]);
        array<ll, 2> now = qry(1, 0, n-1, 0, tin[it]-1);
        now = max(now, qry(1, 0, n-1, tout[it]+1, n-1));
        upd(1, 0, n-1, nxt[1], -w);
        upd(1, 0, n-1, now[1], w);
        ll prev_ans = curr_ans;
        vector<int> del1, added1, del2, added2;
        if(dist.count(now[0])) {
            dist.erase(dist.find(now[0]));
            curr_ans -= now[0];
            del1.push_back(now[0]);
        }
        else if(vals.count(now[0])) {
            vals.erase(vals.find(now[0]));
            del2.push_back(now[0]);
        }
        if(dist.count(nxt[0])) {
            dist.erase(dist.find(nxt[0]));
            curr_ans -= nxt[0];
            del1.push_back(nxt[0]);
        }
        else if(vals.count(nxt[0])){
            vals.erase(vals.find(nxt[0]));
            del2.push_back(nxt[0]);
        }
        vals.insert(now[0]+w);
        vals.insert(nxt[0]-w);
        added2.push_back(now[0]+w);
        added2.push_back(nxt[0]-w);
        while(dist.size() < k) {
            if(vals.empty()) {
                while(1) {

                }
            }
            auto it = *(vals.begin());
            dist.insert(it);
            added1.push_back(it);
            vals.erase(vals.begin());
            curr_ans += it;
        }
        dfs1(it, node);
        upd(1, 0, n-1, nxt[1], w);
        upd(1, 0, n-1, now[1], -w);
        for(auto it : added1) {
            dist.erase(dist.find(it));
            vals.insert(it);
        }
        for(auto it : added2) {
            vals.erase(vals.find(it));
        }
        for(auto it : del1) {
            dist.insert(it);
        }
        for(auto it : del2) {
            vals.insert(it);
        }
        curr_ans = prev_ans;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i < n; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    for(int i = 1; i <= n; i++) {
        build(1, 0, n-1);
        cnt = -1;
        dfs(i, 0);
        fill(tin, tin+n, 0);
        fill(tout, tout+n, 0);
        multiset<ll, greater<ll>> vals;
        for(int i = 0; i < n; i++) {
            array<ll, 2> now = qry(1, 0, n-1, i, i);
            vals.insert(now[0]);
        }
        ll ans = 0;
        int cnt1 = 0;
        for(auto it : vals) {
            ++cnt1;
            ans += it;
            if(cnt1 == k) break;
        }
        cout << ans << '\n';
    }
    /*int cnt = 0; curr_ans = 0;
    for(auto it : vals) {
        ++cnt;
        curr_ans += it;
        dist.insert(it);
        if(cnt == k) break;
    }
    for(auto it : dist) {
        vals.erase(vals.find(it));
    }
    dfs1(1, 0);
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
    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