oj.uz

Submission #503721

# Submission time Handle Problem Language Result Execution time Memory
503721 2022-01-08T17:43:31 Z Stickfish Paths (RMI21_paths) C++17
19 / 100
 600 ms 30936 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 11 ms 6348 KB Output is correct
4 Correct 9 ms 6228 KB Output is correct
5 Correct 30 ms 6708 KB Output is correct
6 Correct 4 ms 5264 KB Output is correct
7 Correct 6 ms 5804 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 11 ms 6348 KB Output is correct
4 Correct 9 ms 6228 KB Output is correct
5 Correct 30 ms 6708 KB Output is correct
6 Correct 4 ms 5264 KB Output is correct
7 Correct 6 ms 5804 KB Output is correct
8 Execution timed out 1083 ms 30936 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 11 ms 6348 KB Output is correct
4 Correct 9 ms 6228 KB Output is correct
5 Correct 30 ms 6708 KB Output is correct
6 Correct 4 ms 5264 KB Output is correct
7 Correct 6 ms 5804 KB Output is correct
8 Execution timed out 1083 ms 30936 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 20116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 11 ms 6348 KB Output is correct
4 Correct 9 ms 6228 KB Output is correct
5 Correct 30 ms 6708 KB Output is correct
6 Correct 4 ms 5264 KB Output is correct
7 Correct 6 ms 5804 KB Output is correct
8 Execution timed out 1083 ms 30936 KB Time limit exceeded
9 Halted 0 ms 0 KB -