oj.uz

Submission #855957

# Submission time Handle Problem Language Result Execution time Memory
855957 2023-10-02T11:44:33 Z lolismek Paths (RMI21_paths) C++14
36 / 100
 600 ms 1016 KB 
#include <iostream>
#include <vector>
 
#define pii pair <long long, int>
 
using namespace std;
 
const int NMAX = 2000;
 
vector <pii> adj[NMAX + 1];
 
int edg[NMAX + 1];
int par[NMAX + 1];
int lin[NMAX + 1];
long long v[NMAX + 1];
pii tm[NMAX + 1];
 
int dfsTime;
void dfs(int node, int parent){
    par[node] = parent;
    lin[++dfsTime] = node;
    tm[node].first = dfsTime;
 
    for(pii child : adj[node]){
        if(child.first != parent){
            edg[child.first] = child.second;
            v[child.first] = v[node] + child.second;
            dfs(child.first, node);
        }
    }
 
    tm[node].second = dfsTime;
}
 
namespace AINT{
    pii aint[4 * NMAX + 1];
    long long lazy[4 * NMAX + 1];
 
    void build(int node, int left, int right){
        lazy[node] = 0;
        if(left == right){
            aint[node] = {v[lin[left]], lin[left]};
            return;
        }
 
        int mid = (left + right) / 2;
        build(2 * node, left, mid);
        build(2 * node + 1, mid + 1, right);
 
        aint[node] = max(aint[2 * node], aint[2 * node + 1]);
    }
 
    void propag(int node, int left, int right){
        aint[node].first += lazy[node];
        if(left < right){
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
 
    void update(int node, int left, int right, int uleft, int uright, int val){
        propag(node, left, right);
 
        if(uleft <= left && right <= uright){
            lazy[node] += val;
            propag(node, left, right);
            return;
        }
 
        int mid = (left + right) / 2;
        if(uleft <= mid){
            update(2 * node, left, mid, uleft, uright, val);
        }
        if(mid + 1 <= uright){
            update(2 * node + 1, mid + 1, right, uleft, uright, val);
        }
 
        propag(2 * node, left, mid);
        propag(2 * node + 1, mid + 1, right);
        aint[node] = max(aint[2 * node], aint[2 * node + 1]);
    }
 
    pii query(int node, int left, int right, int qleft, int qright){
        propag(node, left, right);
 
        if(qleft <= left && right <= qright){
            return aint[node];
        }
 
        int mid = (left + right) / 2;
        pii ans = {0, 0};
 
        if(qleft <= mid){
            ans = query(2 * node, left, mid, qleft, qright);
        }
        if(mid + 1 <= qright){
            ans = max(ans, query(2 * node + 1, mid + 1, right, qleft, qright));
        }
 
        return ans;
    }
}
 
bool used[NMAX + 1];
 
int n, k;
long long solve(int root){
    for(int i = 1; i <= n; i++){
        used[i] = false;
        v[i] = lin[i] = par[i] = edg[i] = 0;
        tm[i].first = tm[i].second = 0;
    }
 
    dfsTime = 0;
    edg[root] = 0;
    dfs(root, 0);
 
    AINT::build(1, 1, n);
 
    long long ans = 0;
    int cnt = 0;
    for(int i = 1; i <= k; i++){
        pii x = AINT::query(1, 1, n, 1, n);
        int node = x.second;
        ans += x.first;
        while(node != 0 && !used[node]){
            ++cnt;
            used[node] = true;
            AINT::update(1, 1, n, tm[node].first, tm[node].second, -edg[node]);
            node = par[node];
        }
    }

    if(cnt > n){
        exit(456);
    }
 
    return ans;
}
 
signed main(){
 
    cin >> n >> k;
 
    for(int i = 1; i <= n - 1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
 
    for(int i = 1; i <= n; i++){
        cout << solve(i) << '\n';
    }
 
    return 0;
}

/*
11 3
1 2 5
2 3 3
2 6 5
3 4 4
3 5 2
1 7 6
7 8 4
7 9 5
1 10 1
10 11 1
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 8 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 8 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 127 ms 852 KB Output is correct
9 Correct 220 ms 680 KB Output is correct
10 Correct 224 ms 644 KB Output is correct
11 Correct 71 ms 600 KB Output is correct
12 Correct 126 ms 636 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 8 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 127 ms 852 KB Output is correct
9 Correct 220 ms 680 KB Output is correct
10 Correct 224 ms 644 KB Output is correct
11 Correct 71 ms 600 KB Output is correct
12 Correct 126 ms 636 KB Output is correct
13 Execution timed out 861 ms 1016 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 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 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 8 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 127 ms 852 KB Output is correct
9 Correct 220 ms 680 KB Output is correct
10 Correct 224 ms 644 KB Output is correct
11 Correct 71 ms 600 KB Output is correct
12 Correct 126 ms 636 KB Output is correct
13 Execution timed out 861 ms 1016 KB Time limit exceeded
14 Halted 0 ms 0 KB -