Submission #503721

#	Time	Username	Problem	Language	Result	Execution time	Memory
503721		Stickfish	Paths (RMI21_paths)	C++17	19 / 100	1083 ms	30936 KiB

Main

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const int MAXN = 100008;
vector<pair<int, ll>> edg[MAXN];
vector<ll> prof[MAXN];
ll ans[MAXN];
int k;

vector<ll> merge(vector<ll> a, vector<ll> b) {
    int n = a.size();
    int m = b.size();
    vector<ll> ans(n + m - 1);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            ans[i + j] = max(ans[i + j], a[i] + b[j]);
        }
    }
    if (k > ans.size())
        ans.resize(k + 1);
    return ans;
}

struct stree {
    void assign(vector<vector<ll>>& v) {
        sz = v.size();
        t.resize(sz * 2 - 1);
        assign(0, 0, sz, v);
    }

    vector<ll> get_full() {
        return t[0];
    }

    vector<ll> get_full_replace(int i, vector<ll> v) {
        return get_full_replace(0, 0, sz, i, v);
    }

 private:
     vector<vector<ll>> t;
     int sz;

     void assign(int ind, int lnd, int rnd, vector<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] = merge(t[ind + 1], t[ind + (mnd - lnd) * 2]);
     }

     vector<ll> get_full_replace(int ind, int lnd, int rnd, int i, vector<ll>& v) {
         if (i < lnd || rnd <= i)
             return t[ind];
         if (rnd - lnd == 1) {
             return v;
         }
         int mnd = (lnd + rnd) / 2;
         return merge(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, 0};
        return;
    }
    vector<vector<ll>> prof_edg;
    for (auto [u, d] : edg[v]) {
        if (u == rt)
            continue;
        dfs(u, v);
        prof_edg.push_back(prof[u]);
        for (auto& x : prof_edg.back()) {
            x += d;
        }
        prof_edg.back()[0] -= d;
    }
    stree tr;
    tr.assign(prof_edg);
    prof[v] = tr.get_full();
    return;
}

void dfs_ans(int v, int rt) {
    if (k >= prof[v].size()) {
        ans[v] = prof[v].back();
    } else {
        ans[v] = prof[v][k];
    }

    vector<vector<ll>> prof_edg;
    for (auto [u, d] : edg[v]) {
        prof_edg.push_back(prof[u]);
        for (auto& x : prof_edg.back()) {
            x += d;
        }
        prof_edg.back()[0] -= 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});

        for (auto& x : prof[v]) {
            x += d;
        }
        prof[v][0] -= d;

        vector<ll> profu = prof[u];
        prof[u] = merge(prof[u], prof[v]);

        for (auto& x : prof[v]) {
            x -= d;
        }
        prof[v][0] += 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 'std::vector<long long int> merge(std::vector<long long int>, std::vector<long long int>)':
Main.cpp:21:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if (k > ans.size())
      |         ~~^~~~~~~~~~~~
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:68:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   68 |     if (edg[v].empty() || edg[v].size() == 1 && edg[v][0].first == rt) {
      |                           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void dfs_ans(int, int)':
Main.cpp:90:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     if (k >= prof[v].size()) {
      |         ~~^~~~~~~~~~~~~~~~~

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