oj.uz

Submission #769577

# Submission time Handle Problem Language Result Execution time Memory
769577 2023-06-29T19:46:58 Z vjudge1 Paths (RMI21_paths) C++17
36 / 100
 600 ms 18280 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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], rep[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 + (ll)(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 dfs2(int x, int p, ll v)
{
    update(1, 0, sz - 1, eul[x], endeul[x], -v);
    update(1, 0, sz - 1, 0, eul[x] - 1, v);
    update(1, 0, sz - 1, endeul[x] + 1, n - 1, v);

    propagate(1, 0, sz - 1);
    rep[x] = st[1].ff;
    for(auto e: adj[x])
    {
        if(e.ff == p)
            continue;
        dfs2(e.ff, x, e.ss);
    }

    update(1, 0, sz - 1, eul[x], endeul[x], v);
    update(1, 0, sz - 1, 0, eul[x] - 1, -v);
    update(1, 0, sz - 1, endeul[x] + 1, n - 1, -v);
}
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);
    dfs2(1, 0, 0);
    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
        {
            cout << rep[root] << '\n';
        }
    }
}

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 6 ms 2644 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 8 ms 2680 KB Output is correct
7 Correct 7 ms 2740 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 6 ms 2644 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 8 ms 2680 KB Output is correct
7 Correct 7 ms 2740 KB Output is correct
8 Correct 112 ms 2836 KB Output is correct
9 Correct 172 ms 2892 KB Output is correct
10 Correct 207 ms 2856 KB Output is correct
11 Correct 75 ms 2856 KB Output is correct
12 Correct 127 ms 2832 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 6 ms 2644 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 8 ms 2680 KB Output is correct
7 Correct 7 ms 2740 KB Output is correct
8 Correct 112 ms 2836 KB Output is correct
9 Correct 172 ms 2892 KB Output is correct
10 Correct 207 ms 2856 KB Output is correct
11 Correct 75 ms 2856 KB Output is correct
12 Correct 127 ms 2832 KB Output is correct
13 Execution timed out 826 ms 2996 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 18280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 6 ms 2644 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 8 ms 2680 KB Output is correct
7 Correct 7 ms 2740 KB Output is correct
8 Correct 112 ms 2836 KB Output is correct
9 Correct 172 ms 2892 KB Output is correct
10 Correct 207 ms 2856 KB Output is correct
11 Correct 75 ms 2856 KB Output is correct
12 Correct 127 ms 2832 KB Output is correct
13 Execution timed out 826 ms 2996 KB Time limit exceeded
14 Halted 0 ms 0 KB -