oj.uz

Submission #769581

# Submission time Handle Problem Language Result Execution time Memory
769581 2023-06-29T19:50:25 Z MohamedAliSaidane Paths (RMI21_paths) C++14
36 / 100
 600 ms 19148 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<pll> 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);

    rep[x] = query(1, 0 , k - 1, 0, n - 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 2644 KB Output is correct
2 Correct 1 ms 2660 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2660 KB Output is correct
3 Correct 5 ms 2740 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 4 ms 2740 KB Output is correct
6 Correct 8 ms 2644 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 112 ms 2840 KB Output is correct
9 Correct 171 ms 2900 KB Output is correct
10 Correct 185 ms 2864 KB Output is correct
11 Correct 71 ms 2844 KB Output is correct
12 Correct 128 ms 2848 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2660 KB Output is correct
3 Correct 5 ms 2740 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 4 ms 2740 KB Output is correct
6 Correct 8 ms 2644 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 112 ms 2840 KB Output is correct
9 Correct 171 ms 2900 KB Output is correct
10 Correct 185 ms 2864 KB Output is correct
11 Correct 71 ms 2844 KB Output is correct
12 Correct 128 ms 2848 KB Output is correct
13 Execution timed out 784 ms 2976 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 19148 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 2644 KB Output is correct
2 Correct 1 ms 2660 KB Output is correct
3 Correct 5 ms 2740 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 4 ms 2740 KB Output is correct
6 Correct 8 ms 2644 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 112 ms 2840 KB Output is correct
9 Correct 171 ms 2900 KB Output is correct
10 Correct 185 ms 2864 KB Output is correct
11 Correct 71 ms 2844 KB Output is correct
12 Correct 128 ms 2848 KB Output is correct
13 Execution timed out 784 ms 2976 KB Time limit exceeded
14 Halted 0 ms 0 KB -