Submission #1224574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224574		jordan	Paths (RMI21_paths)	C++20	12 / 100	312 ms	25708 KiB

Main

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

const int mxN = 3e5+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 mx = *(dist.begin()), mn = *(prev(dist.end()));
        if(mx >= now[0] && mn <= now[0] && dist.count(now[0])) {
            dist.erase(dist.find(now[0]));
            curr_ans -= now[0];
        }
        else if(vals.count(now[0])) vals.erase(vals.find(now[0]));
        if(mx >= nxt[0] && mn <= nxt[0] && dist.count(nxt[0])) {
            dist.erase(dist.find(nxt[0]));
            curr_ans -= nxt[0];
        }
        else if(vals.count(nxt[0])) vals.erase(vals.find(nxt[0]));
        vals.insert(now[0]+w);
        vals.insert(nxt[0]-w);
        while(dist.size() < k && vals.size()) {
            auto it = *(vals.begin());
            dist.insert(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);
        ll mx1 = *(dist.begin()), mn1 = *(prev(dist.end()));
        if(mx1 >= now[0]+w && mn1 <= now[0]+w && dist.count(now[0]+w)) {
            dist.erase(dist.find(now[0]+w));
            curr_ans -= (now[0]+w);
        }
        else if(vals.count(now[0]+w)) vals.erase(vals.find(now[0]+w));
        if(mx1 >= nxt[0]-w && mn1 <= nxt[0]-w && dist.count(nxt[0]-w)) {
            dist.erase(dist.find(nxt[0]-w));
            curr_ans -= (nxt[0]-w);
        }
        else if(vals.count(nxt[0]-w)) vals.erase(vals.find(nxt[0]-w));
        vals.insert(now[0]);
        vals.insert(nxt[0]);
        while(dist.size() < k) {
            auto it = *(vals.begin());
            dist.insert(it);
            curr_ans += it;
            vals.erase(vals.begin());
        }
        while(!vals.empty()) {
            ll f = *(vals.begin()), s = *(prev(dist.end()));
            if(f > s) {
                dist.insert(f);
                dist.erase(dist.find(s));
                vals.erase(vals.find(f));
                vals.insert(s);
                curr_ans -= s; curr_ans += f;
            }
            else break;
        }
    }
}

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});
    }
    build(1, 0, n-1);
    dfs(1, 0);
    for(int i = 0; i <= cnt; i++) {
        array<ll, 2> now = qry(1, 0, n-1, i, i);
        vals.insert(now[0]);
    }
    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: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32