oj.uz

Submission #503729

# Submission time Handle Problem Language Result Execution time Memory
503729 2022-01-08T18:13:28 Z Stickfish Paths (RMI21_paths) C++17
12 / 100
 204 ms 16772 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 (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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 1 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 1 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 1 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 10376 KB Output is correct
2 Correct 154 ms 16772 KB Output is correct
3 Correct 139 ms 10440 KB Output is correct
4 Correct 152 ms 10844 KB Output is correct
5 Correct 204 ms 14684 KB Output is correct
6 Correct 140 ms 10520 KB Output is correct

Subtask #6
0 / 32.0

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