Submission #855958

#	Time	Username	Problem	Language	Result	Execution time	Memory
855958		lolismek	Paths (RMI21_paths)	C++14	36 / 100	785 ms	788 KiB

Main

#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 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32