oj.uz

Submission #855954

# Submission time Handle Problem Language Result Execution time Memory
855954 2023-10-02T11:40:26 Z lolismek Paths (RMI21_paths) C++14
36 / 100
 600 ms 920 KB 
#include <iostream>
#include <vector>
 
#define int long long
#define pii pair <int, 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];
int 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];
    int 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;
int 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);
 
    int 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 348 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 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 7 ms 548 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 8 ms 344 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 0 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 7 ms 548 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 120 ms 736 KB Output is correct
9 Correct 214 ms 696 KB Output is correct
10 Correct 209 ms 604 KB Output is correct
11 Correct 70 ms 604 KB Output is correct
12 Correct 126 ms 920 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 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 7 ms 548 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 120 ms 736 KB Output is correct
9 Correct 214 ms 696 KB Output is correct
10 Correct 209 ms 604 KB Output is correct
11 Correct 70 ms 604 KB Output is correct
12 Correct 126 ms 920 KB Output is correct
13 Execution timed out 841 ms 828 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 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 7 ms 548 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 120 ms 736 KB Output is correct
9 Correct 214 ms 696 KB Output is correct
10 Correct 209 ms 604 KB Output is correct
11 Correct 70 ms 604 KB Output is correct
12 Correct 126 ms 920 KB Output is correct
13 Execution timed out 841 ms 828 KB Time limit exceeded
14 Halted 0 ms 0 KB -