oj.uz

Submission #769578

# Submission time Handle Problem Language Result Execution time Memory
769578 2023-06-29T19:47:28 Z MohamedAliSaidane Paths (RMI21_paths) C++14
36 / 100
 600 ms 17612 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 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 5 ms 2732 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 2740 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 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 5 ms 2732 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 2740 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 112 ms 2832 KB Output is correct
9 Correct 175 ms 2872 KB Output is correct
10 Correct 202 ms 2772 KB Output is correct
11 Correct 69 ms 2840 KB Output is correct
12 Correct 135 ms 2836 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 5 ms 2732 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 2740 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 112 ms 2832 KB Output is correct
9 Correct 175 ms 2872 KB Output is correct
10 Correct 202 ms 2772 KB Output is correct
11 Correct 69 ms 2840 KB Output is correct
12 Correct 135 ms 2836 KB Output is correct
13 Execution timed out 787 ms 2964 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 5 ms 2732 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 2740 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 112 ms 2832 KB Output is correct
9 Correct 175 ms 2872 KB Output is correct
10 Correct 202 ms 2772 KB Output is correct
11 Correct 69 ms 2840 KB Output is correct
12 Correct 135 ms 2836 KB Output is correct
13 Execution timed out 787 ms 2964 KB Time limit exceeded
14 Halted 0 ms 0 KB -