oj.uz

Submission #717934

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

vector<pair<int, ll>> v[2001];
ll b[2001], par[2001], edge[2001][2001];
bool vis[2001];
priority_queue<pair<ll, int>> pq;

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);

    int n, kk;
    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});
    }
    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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 8 ms 1236 KB Output is correct
4 Correct 8 ms 1276 KB Output is correct
5 Correct 8 ms 1236 KB Output is correct
6 Correct 11 ms 1296 KB Output is correct
7 Correct 10 ms 1236 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 8 ms 1236 KB Output is correct
4 Correct 8 ms 1276 KB Output is correct
5 Correct 8 ms 1236 KB Output is correct
6 Correct 11 ms 1296 KB Output is correct
7 Correct 10 ms 1236 KB Output is correct
8 Correct 279 ms 6124 KB Output is correct
9 Correct 221 ms 6544 KB Output is correct
10 Correct 325 ms 6712 KB Output is correct
11 Correct 162 ms 5480 KB Output is correct
12 Correct 246 ms 6580 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 8 ms 1236 KB Output is correct
4 Correct 8 ms 1276 KB Output is correct
5 Correct 8 ms 1236 KB Output is correct
6 Correct 11 ms 1296 KB Output is correct
7 Correct 10 ms 1236 KB Output is correct
8 Correct 279 ms 6124 KB Output is correct
9 Correct 221 ms 6544 KB Output is correct
10 Correct 325 ms 6712 KB Output is correct
11 Correct 162 ms 5480 KB Output is correct
12 Correct 246 ms 6580 KB Output is correct
13 Execution timed out 1084 ms 13480 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 8 ms 1236 KB Output is correct
4 Correct 8 ms 1276 KB Output is correct
5 Correct 8 ms 1236 KB Output is correct
6 Correct 11 ms 1296 KB Output is correct
7 Correct 10 ms 1236 KB Output is correct
8 Correct 279 ms 6124 KB Output is correct
9 Correct 221 ms 6544 KB Output is correct
10 Correct 325 ms 6712 KB Output is correct
11 Correct 162 ms 5480 KB Output is correct
12 Correct 246 ms 6580 KB Output is correct
13 Execution timed out 1084 ms 13480 KB Time limit exceeded
14 Halted 0 ms 0 KB -