oj.uz

Submission #717953

# Submission time Handle Problem Language Result Execution time Memory
717953 2023-04-02T22:43:10 Z vjudge1 Paths (RMI21_paths) C++17
48 / 100
 600 ms 22556 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[100001];
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 > 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;
    val = g, Left = 1, Right = n * 2;
    update();
    val = g * -2, Left = be[x] + 1, Right = en[x] + 1;
    update();
    sol[x] = seg[1];
    for(auto [y, z] : v[x]) {
        if(!vis[y])
            solve(y, z);
    }
    val = g * 2, Left = be[x] + 1, Right = en[x] + 1;
    update();
    val = -g, Left = 1, 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 1 ms 2644 KB Output is correct
2 Correct 2 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 2 ms 2644 KB Output is correct
3 Correct 10 ms 3540 KB Output is correct
4 Correct 9 ms 3620 KB Output is correct
5 Correct 8 ms 3540 KB Output is correct
6 Correct 12 ms 3632 KB Output is correct
7 Correct 11 ms 3612 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 2 ms 2644 KB Output is correct
3 Correct 10 ms 3540 KB Output is correct
4 Correct 9 ms 3620 KB Output is correct
5 Correct 8 ms 3540 KB Output is correct
6 Correct 12 ms 3632 KB Output is correct
7 Correct 11 ms 3612 KB Output is correct
8 Correct 272 ms 8396 KB Output is correct
9 Correct 211 ms 8840 KB Output is correct
10 Correct 321 ms 9036 KB Output is correct
11 Correct 168 ms 7748 KB Output is correct
12 Correct 258 ms 9000 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 2 ms 2644 KB Output is correct
3 Correct 10 ms 3540 KB Output is correct
4 Correct 9 ms 3620 KB Output is correct
5 Correct 8 ms 3540 KB Output is correct
6 Correct 12 ms 3632 KB Output is correct
7 Correct 11 ms 3612 KB Output is correct
8 Correct 272 ms 8396 KB Output is correct
9 Correct 211 ms 8840 KB Output is correct
10 Correct 321 ms 9036 KB Output is correct
11 Correct 168 ms 7748 KB Output is correct
12 Correct 258 ms 9000 KB Output is correct
13 Execution timed out 1089 ms 15624 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 18904 KB Output is correct
2 Correct 174 ms 22556 KB Output is correct
3 Correct 145 ms 20832 KB Output is correct
4 Correct 154 ms 20808 KB Output is correct
5 Correct 187 ms 21708 KB Output is correct
6 Correct 142 ms 20804 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 10 ms 3540 KB Output is correct
4 Correct 9 ms 3620 KB Output is correct
5 Correct 8 ms 3540 KB Output is correct
6 Correct 12 ms 3632 KB Output is correct
7 Correct 11 ms 3612 KB Output is correct
8 Correct 272 ms 8396 KB Output is correct
9 Correct 211 ms 8840 KB Output is correct
10 Correct 321 ms 9036 KB Output is correct
11 Correct 168 ms 7748 KB Output is correct
12 Correct 258 ms 9000 KB Output is correct
13 Execution timed out 1089 ms 15624 KB Time limit exceeded
14 Halted 0 ms 0 KB -