oj.uz

Submission #769513

# Submission time Handle Problem Language Result Execution time Memory
769513 2023-06-29T17:13:18 Z MohamedAliSaidane Paths (RMI21_paths) C++14
36 / 100
 600 ms 16844 KB 
#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 = st[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.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 2724 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 9 ms 2716 KB Output is correct
7 Correct 7 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 2724 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 9 ms 2716 KB Output is correct
7 Correct 7 ms 2644 KB Output is correct
8 Correct 123 ms 2928 KB Output is correct
9 Correct 195 ms 2828 KB Output is correct
10 Correct 204 ms 2812 KB Output is correct
11 Correct 74 ms 2824 KB Output is correct
12 Correct 124 ms 2816 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 2724 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 9 ms 2716 KB Output is correct
7 Correct 7 ms 2644 KB Output is correct
8 Correct 123 ms 2928 KB Output is correct
9 Correct 195 ms 2828 KB Output is correct
10 Correct 204 ms 2812 KB Output is correct
11 Correct 74 ms 2824 KB Output is correct
12 Correct 124 ms 2816 KB Output is correct
13 Execution timed out 860 ms 3060 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 248 ms 16844 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 2724 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 9 ms 2716 KB Output is correct
7 Correct 7 ms 2644 KB Output is correct
8 Correct 123 ms 2928 KB Output is correct
9 Correct 195 ms 2828 KB Output is correct
10 Correct 204 ms 2812 KB Output is correct
11 Correct 74 ms 2824 KB Output is correct
12 Correct 124 ms 2816 KB Output is correct
13 Execution timed out 860 ms 3060 KB Time limit exceeded
14 Halted 0 ms 0 KB -