oj.uz

Submission #855958

# Submission time Handle Problem Language Result Execution time Memory
855958 2023-10-02T11:45:24 Z lolismek Paths (RMI21_paths) C++14
36 / 100
 600 ms 788 KB 
#include <iostream>
#include <vector>
 
#pragma GCC optimize("Ofast")
#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 0 ms 348 KB Output is correct
2 Correct 0 ms 376 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 6 ms 536 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 8 ms 544 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 115 ms 636 KB Output is correct
9 Correct 204 ms 656 KB Output is correct
10 Correct 200 ms 644 KB Output is correct
11 Correct 64 ms 636 KB Output is correct
12 Correct 117 ms 788 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 6 ms 536 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 8 ms 544 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 115 ms 636 KB Output is correct
9 Correct 204 ms 656 KB Output is correct
10 Correct 200 ms 644 KB Output is correct
11 Correct 64 ms 636 KB Output is correct
12 Correct 117 ms 788 KB Output is correct
13 Execution timed out 785 ms 772 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 0 ms 348 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 6 ms 536 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 8 ms 544 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 115 ms 636 KB Output is correct
9 Correct 204 ms 656 KB Output is correct
10 Correct 200 ms 644 KB Output is correct
11 Correct 64 ms 636 KB Output is correct
12 Correct 117 ms 788 KB Output is correct
13 Execution timed out 785 ms 772 KB Time limit exceeded
14 Halted 0 ms 0 KB -