Submission #503729

#	Time	Username	Problem	Language	Result	Execution time	Memory
503729		Stickfish	Paths (RMI21_paths)	C++17	12 / 100	204 ms	16772 KiB

Main

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
 
const int MAXN = 100008;
vector<pair<int, ll>> edg[MAXN];
ll prof[MAXN];
ll ans[MAXN];
int k;
 
struct stree {
    void assign(vector<ll>& v) {
        sz = v.size();
        t.resize(sz * 2 - 1);
        assign(0, 0, sz, v);
    }
 
    ll get_full() {
        return t[0];
    }
 
    ll get_full_replace(int i, ll v) {
        return get_full_replace(0, 0, sz, i, v);
    }
 
 private:
     vector<ll> t;
     int sz;
 
     void assign(int ind, int lnd, int rnd, vector<ll>& v) {
         if (rnd - lnd == 1) {
             t[ind] = v[lnd];
             return;
         }
         int mnd = (lnd + rnd) / 2;
         assign(ind + 1, lnd, mnd, v);
         assign(ind + (mnd - lnd) * 2, mnd, rnd, v);
         t[ind] = max(t[ind + 1], t[ind + (mnd - lnd) * 2]);
     }
 
     ll get_full_replace(int ind, int lnd, int rnd, int i, ll& v) {
         if (i < lnd || rnd <= i)
             return t[ind];
         if (rnd - lnd == 1) {
             return v;
         }
         int mnd = (lnd + rnd) / 2;
         return max(get_full_replace(ind + 1, lnd, mnd, i, v), get_full_replace(ind + (mnd - lnd) * 2, mnd, rnd, i, v));
     }
};
 
void dfs(int v, int rt) {
    if (edg[v].empty() || edg[v].size() == 1 && edg[v][0].first == rt) {
        prof[v] = 0;
        return;
    }
    vector<ll> prof_edg;
    for (auto [u, d] : edg[v]) {
        if (u == rt)
            continue;
        dfs(u, v);
        prof_edg.push_back(prof[u]);
        prof_edg.back() += d;
    }
    stree tr;
    tr.assign(prof_edg);
    prof[v] = tr.get_full();
    return;
}
 
void dfs_ans(int v, int rt) {
    ans[v] = prof[v];
    //if (k >= prof[v].size()) {
        //ans[v] = prof[v].back();
    //} else {
        //ans[v] = prof[v][k];
    //}
 
    vector<ll> prof_edg;
    for (auto [u, d] : edg[v]) {
        prof_edg.push_back(prof[u]);
        prof_edg.back() += d;
    }
    stree tr;
    tr.assign(prof_edg);
 
    int n = edg[v].size();
    for (int i = 0; i < n; ++i) {
        auto [u, d] = edg[v][i];
        if (u == rt)
            continue;
 
        prof[v] = tr.get_full_replace(i, 0);
 
        prof[v] += d;
 
        ll profu = prof[u];
        prof[u] = max(prof[u], prof[v]);
 
        prof[v] -= d;
 
        dfs_ans(u, v);
        prof[u] = profu;
    }
    prof[v] = tr.get_full();
}
 
signed main() {
    int n;
    cin >> n >> k;
    for (int i = 0; i + 1 < n; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        --u, --v;
        edg[u].push_back({v, c});
        edg[v].push_back({u, c});
    }
    dfs(0, -1);
    dfs_ans(0, -1);
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << '\n';
    }
    //for (int i = 0; i < n; ++i) {
        //dfs(i, -1);
        //if (k >= prof[i].size())
            //cout << prof[i].back() << '\n';
        //else
            //cout << prof[i][k] << '\n';
    //}
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:54:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   54 |     if (edg[v].empty() || edg[v].size() == 1 && edg[v][0].first == rt) {
      |                           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32