oj.uz

Submission #503725

# Submission time Handle Problem Language Result Execution time Memory
503725 2022-01-08T18:02:17 Z Stickfish Paths (RMI21_paths) C++17
0 / 100
 86 ms 10476 KB 
#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 (rnd - lnd == 1) {
             return v;
         }
         int mnd = (lnd + rnd) / 2;
         if (i < mnd) {
             return max(get_full_replace(ind + 1, lnd, mnd, i, v), t[ind + (mnd - lnd) * 2]);
         } else {
             return max(t[ind + 1], get_full_replace(ind + (mnd - lnd), 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;
    }
    prof[v] = {0};
    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() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    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

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 10476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -