oj.uz

Submission #717947

# Submission time Handle Problem Language Result Execution time Memory
717947 2023-04-02T22:23:59 Z vjudge1 Paths (RMI21_paths) C++17
36 / 100
 600 ms 17800 KB 
#include "bits/stdc++.h"
#define ll long long
using namespace std;
const ll mod = 1000000007;

ll N, Left, Right, val, n, kk;
vector<pair<int, ll>> v[100001];
ll b[100001], par[100001], edge[2001][2001], be[100001], en[100001], seg[1000000], lazy[1000000], sol[100001];
bool vis[2001];
priority_queue<pair<ll, int>> pq;
int indd;

void spread(int ind) {
    seg[ind * 2] += lazy[ind];
    seg[ind * 2 + 1] += lazy[ind];
    lazy[ind * 2] += lazy[ind];
    lazy[ind * 2 + 1] += lazy[ind];
    lazy[ind] = 0;
}

void update(int l = 1, int r = N, int ind = 1) {
    if(l > r || l > Right || r < Left)
        return;
    if(l != r)
        spread(ind);
    if(l >= Left && r <= Right) {
        seg[ind] += val;
        lazy[ind] += val;
        return;
    }
    int mid = (l + r) / 2;
    update(l, mid, ind * 2);
    update(mid + 1, r, ind * 2 + 1);
    seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
}

void dfs2(int x) {
    vis[x] = 1;
    be[x] = indd;
    seg[indd + N] = b[x];
    indd++;
    for(auto [y, z] : v[x]) {
        if(!vis[y]) {
            b[y] = b[x] + z;
            dfs2(y);
        }
    }
    en[x] = indd;
    seg[indd + N] = b[x];
    indd++;
}

void solve(int x, ll g) {
    vis[x] = 1;
    int l = be[x] + 2, r = en[x];
    val = -g, Left = l, Right = r;
    update();
    Left = 1, Right = l - 2;
    val *= -1;
    update();
    Left = r + 2, Right = n * 2;
    update();
    sol[x] = seg[1];
    for(auto [y, z] : v[x]) {
        if(!vis[y])
            solve(y, z);
    }
    val = g, Left = l, Right = r;
    update();
    Left = 1, Right = l - 2;
    val *= -1;
    update();
    Left = r + 2, Right = n * 2;
    update();
}

void dfs(int x) {
    vis[x] = 1;
    for(auto [y, z] : v[x]) {
        if(!vis[y]) {
            par[y] = x;
            b[y] = b[x] + z;
            pq.push({b[y], y});
            dfs(y);
        }
    }
}

ll idk1(int x) {
    ll ans = 0;
    while(par[x]) {
        if(edge[x][par[x]] == -1)
            break;
        ans += edge[x][par[x]];
        x = par[x];
    }
    return ans;
}

void idk2(int x) {
    while(par[x]) {
        if(edge[x][par[x]] == -1)
            break;
        edge[x][par[x]] = edge[par[x]][x] = -1;
        x = par[x];
    }
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("cowland.in","r",stdin);
    // freopen("cowland.out","w",stdout);

    cin >> n >> kk;
    for(int i = 0; i < n - 1; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    if(kk == 1) {
        N = exp2(ceil(log2(n * 2)));
        dfs2(1);
        for(int i = 1; i <= n; i++)
            vis[i] = 0;
        for(int i = N - 1; i >= 1; i--)
            seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
        solve(1, 0);
        for(int i = 1; i <= n; i++)
            cout << sol[i] << "\n";
        return 0;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            vis[j] = 0;
            for(auto [k, val] : v[j])
                edge[j][k] = val;
        }
        while(!pq.empty())
            pq.pop();
        par[i] = b[i] = 0;
        dfs(i);
        ll k = kk, ans = 0;
        while(k--) {
            ll val = pq.top().first, x = pq.top().second;
            pq.pop();
            ll y = idk1(x);
            while(y != val) {
                pq.push({y, x});
                val = pq.top().first, x = pq.top().second;
                pq.pop();
                y = idk1(x);
            }
            ans += val;
            idk2(x);
        }
        cout << ans << "\n";
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 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 2 ms 2676 KB Output is correct
3 Correct 9 ms 3540 KB Output is correct
4 Correct 10 ms 3540 KB Output is correct
5 Correct 8 ms 3540 KB Output is correct
6 Correct 10 ms 3540 KB Output is correct
7 Correct 10 ms 3540 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 2 ms 2676 KB Output is correct
3 Correct 9 ms 3540 KB Output is correct
4 Correct 10 ms 3540 KB Output is correct
5 Correct 8 ms 3540 KB Output is correct
6 Correct 10 ms 3540 KB Output is correct
7 Correct 10 ms 3540 KB Output is correct
8 Correct 291 ms 8404 KB Output is correct
9 Correct 243 ms 8824 KB Output is correct
10 Correct 322 ms 9000 KB Output is correct
11 Correct 166 ms 7756 KB Output is correct
12 Correct 248 ms 8964 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 2 ms 2676 KB Output is correct
3 Correct 9 ms 3540 KB Output is correct
4 Correct 10 ms 3540 KB Output is correct
5 Correct 8 ms 3540 KB Output is correct
6 Correct 10 ms 3540 KB Output is correct
7 Correct 10 ms 3540 KB Output is correct
8 Correct 291 ms 8404 KB Output is correct
9 Correct 243 ms 8824 KB Output is correct
10 Correct 322 ms 9000 KB Output is correct
11 Correct 166 ms 7756 KB Output is correct
12 Correct 248 ms 8964 KB Output is correct
13 Execution timed out 1086 ms 15672 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 17800 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 2 ms 2676 KB Output is correct
3 Correct 9 ms 3540 KB Output is correct
4 Correct 10 ms 3540 KB Output is correct
5 Correct 8 ms 3540 KB Output is correct
6 Correct 10 ms 3540 KB Output is correct
7 Correct 10 ms 3540 KB Output is correct
8 Correct 291 ms 8404 KB Output is correct
9 Correct 243 ms 8824 KB Output is correct
10 Correct 322 ms 9000 KB Output is correct
11 Correct 166 ms 7756 KB Output is correct
12 Correct 248 ms 8964 KB Output is correct
13 Execution timed out 1086 ms 15672 KB Time limit exceeded
14 Halted 0 ms 0 KB -