oj.uz

답안 #717947

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 138 ms 17800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 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 -