Submission #769514

#	Time	Username	Problem	Language	Result	Execution time	Memory
769514		vjudge1	Paths (RMI21_paths)	C++17	36 / 100	858 ms	16872 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define ss second
#define ff first
#define all(x) (x).begin(), (x).end()

const int nax = 1e5 + 4;
int n, k, sz = 1;
vector<pii> adj[nax];
vector<pll> st;
vector<ll> lazy;
ll d[nax];
int dpar[nax];
int par[nax], vis[nax], eul[nax], endeul[nax], cor[nax];
int cureul = -1;
void dfs(int x, ll curd, int p)
{
    par[x] = p;
    d[x] = curd;
    dpar[x] = curd - d[p];
    vis[x] = 0;
    eul[x] = ++cureul;
    cor[cureul] = x;
    for(auto e: adj[x])
    {
        if(e.ff == p)
            continue;
        dfs(e.ff, curd + e.ss, x);
    }
    endeul[x] = cureul;
}
void build(int p, int l, int r)
{
    if(l == r)
    {
        st[p] = {d[cor[l]], cor[l]};
        lazy[p] = 0ll;
        return ;
    }
    build(2 * p, l, (l + r)/2);
    build(2 * p + 1, (l + r)/2  + 1, r);
    st[p] = max(st[2 * p], st[2 * p + 1]);
    lazy[p] = 0ll;
}
void propagate(int p, int l, int r)
{
    if(lazy[p])
    {
        if(l != r)
        {
            lazy[2 * p] += lazy[p];
            lazy[2 * p + 1] += lazy[p];
        }
        st[p].ff += lazy[p];
        lazy[p] = 0ll;
    }
}
void update(int p, int l, int r, int i, int j, ll val)
{
    propagate(p, l, r);
    if(i > j)
        return ;
    if(l >= i && r <= j)
    {
        lazy[p] += val;
        propagate(p, l, r);
        return ;
    }
    int m = (l + r)/2;
    update(2 * p, l, m, i, min(j, m), val);
    update(2 * p + 1, m + 1, r, max(i, m + 1), j, val);
    pll a ={st[2 * p].ff + lazy[2 * p], st[2 * p].ss} ;
    pll b ={st[2 * p + 1].ff + lazy[2 * p + 1], st[2 * p + 1].ss};
    st[p] = max(a,b);
    return ;
}
pll query(int p, int l, int r, int i, int j)
{
    propagate(p, l, r);
    if(i > j)
        return {0ll, 0ll};
    if(l >= i && r <= j)
        return st[p];
    int m = (l + r)/2;
    return max(query(2 * p, l, m, i, min(j, m)),
               query(2 * p + 1, m + 1, r, max(i, m + 1), j));
}
void solve()
{
    cin >> n >> k;
    for(int i=  1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        ll c; cin >> c;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }
    dfs(1, 0, 0);
    while(sz < n)
        sz = (sz << 1);
    lazy.assign(2 * sz + 1, 0);
    st.assign(2 * sz + 1, {0, 0});
    build(1, 0, sz - 1);
    for(int root = 1; root <= n; root++)
    {

        if(k > 1)
        {
            cureul = -1;
            dfs(root, 0, 0);
            build(1, 0, sz - 1);
            vis[root] = 1;
            ll ans = 0ll;
            for(int i = 1;i <= k; i++)
            {
                propagate(1, 0, sz - 1);
                pll o = st[1];
                if(o.ff == 0)
                    break;
                int cur = o.ss;
                ans += o.ff;
                while(!vis[cur])
                {
                    update(1, 0, sz - 1, eul[cur], endeul[cur], -dpar[cur]);
                    vis[cur] = 1;
                    cur=  par[cur];
                }
            }
            cout << ans << '\n';
        }
        else
        {
            update(1, 0, sz - 1, eul[root], endeul[root], -d[root]);
            update(1, 0, sz - 1, 0, eul[root] - 1, d[root]);
            update(1, 0, sz - 1, endeul[root] + 1, n - 1, d[root]);

            propagate(1, 0, sz - 1);
            pll o = query(1, 0, sz - 1, 0, n - 1);
            cout << o.ff << '\n';

            update(1, 0, sz - 1, eul[root], endeul[root], d[root]);
            update(1, 0, sz - 1, 0, eul[root] - 1, -d[root]);
            update(1, 0, sz - 1, endeul[root] + 1, n - 1, -d[root]);
        }
    }
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tt = 1;
    while(tt--)
        solve();
}

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