oj.uz

Submission #855956

# Submission time Handle Problem Language Result Execution time Memory
855956 2023-10-02T11:43:34 Z lolismek Paths (RMI21_paths) C++14
36 / 100
 600 ms 856 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;
    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]){
            used[node] = true;
            AINT::update(1, 1, n, tm[node].first, tm[node].second, -edg[node]);
            node = par[node];
        }
    }
 
    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 348 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 348 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 544 KB Output is correct
7 Correct 6 ms 412 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 544 KB Output is correct
7 Correct 6 ms 412 KB Output is correct
8 Correct 129 ms 856 KB Output is correct
9 Correct 221 ms 604 KB Output is correct
10 Correct 226 ms 656 KB Output is correct
11 Correct 73 ms 632 KB Output is correct
12 Correct 124 ms 644 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 544 KB Output is correct
7 Correct 6 ms 412 KB Output is correct
8 Correct 129 ms 856 KB Output is correct
9 Correct 221 ms 604 KB Output is correct
10 Correct 226 ms 656 KB Output is correct
11 Correct 73 ms 632 KB Output is correct
12 Correct 124 ms 644 KB Output is correct
13 Execution timed out 871 ms 852 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 600 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 348 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 544 KB Output is correct
7 Correct 6 ms 412 KB Output is correct
8 Correct 129 ms 856 KB Output is correct
9 Correct 221 ms 604 KB Output is correct
10 Correct 226 ms 656 KB Output is correct
11 Correct 73 ms 632 KB Output is correct
12 Correct 124 ms 644 KB Output is correct
13 Execution timed out 871 ms 852 KB Time limit exceeded
14 Halted 0 ms 0 KB -