oj.uz

Submission #769583

# Submission time Handle Problem Language Result Execution time Memory
769583 2023-06-29T19:52:57 Z MohamedAliSaidane Paths (RMI21_paths) C++14
36 / 100
 600 ms 18948 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);
    if(eul[x] != 0)
        update(1, 0, sz - 1, 0, eul[x] - 1, v);
    if(endeul[x] != n - 1)
    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);
    if(eul[x] != 0)
    update(1, 0, sz - 1, 0, eul[x] - 1, -v);
    if(endeul[x] != n - 1)
    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 2644 KB Output is correct
4 Correct 7 ms 2740 KB Output is correct
5 Correct 4 ms 2744 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 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 5 ms 2644 KB Output is correct
4 Correct 7 ms 2740 KB Output is correct
5 Correct 4 ms 2744 KB Output is correct
6 Correct 8 ms 2644 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 115 ms 2848 KB Output is correct
9 Correct 171 ms 2892 KB Output is correct
10 Correct 181 ms 2852 KB Output is correct
11 Correct 68 ms 2772 KB Output is correct
12 Correct 122 ms 2856 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 2644 KB Output is correct
4 Correct 7 ms 2740 KB Output is correct
5 Correct 4 ms 2744 KB Output is correct
6 Correct 8 ms 2644 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 115 ms 2848 KB Output is correct
9 Correct 171 ms 2892 KB Output is correct
10 Correct 181 ms 2852 KB Output is correct
11 Correct 68 ms 2772 KB Output is correct
12 Correct 122 ms 2856 KB Output is correct
13 Execution timed out 814 ms 2980 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 18948 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 2644 KB Output is correct
4 Correct 7 ms 2740 KB Output is correct
5 Correct 4 ms 2744 KB Output is correct
6 Correct 8 ms 2644 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 115 ms 2848 KB Output is correct
9 Correct 171 ms 2892 KB Output is correct
10 Correct 181 ms 2852 KB Output is correct
11 Correct 68 ms 2772 KB Output is correct
12 Correct 122 ms 2856 KB Output is correct
13 Execution timed out 814 ms 2980 KB Time limit exceeded
14 Halted 0 ms 0 KB -