oj.uz

Submission #503730

# Submission time Handle Problem Language Result Execution time Memory
503730 2022-01-08T18:16:10 Z Stickfish Paths (RMI21_paths) C++17
48 / 100
 600 ms 16676 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;

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]);
        }
    }
    return ans;
}

vector<ll> dfs_(int v, int rt) {
    if (edg[v].empty() || edg[v].size() == 1 && edg[v][0].first == rt) {
        return {0, 0};
    }
    vector<vector<ll>> prof_edg;
    for (auto [u, d] : edg[v]) {
        if (u == rt)
            continue;
        prof_edg.push_back(dfs_(u, v));
        for (auto& x : prof_edg.back()) {
            x += d;
        }
        prof_edg.back()[0] -= d;
    }
    while (prof_edg.size() > 1) {
        int n = prof_edg.size();
        vector<vector<ll>> new_profedg;
        for (int i = 0; i + 1 < n; i += 2) {
            new_profedg.push_back(merge(prof_edg[i], prof_edg[i + 1]));
        }
        if (n % 2) {
            new_profedg.push_back(prof_edg.back());
        }
        prof_edg = new_profedg;
    }
    return prof_edg.back();
}
 
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});
    }
    if (k == 1) {
        dfs(0, -1);
        dfs_ans(0, -1);
        for (int i = 0; i < n; ++i) {
            cout << ans[i] << '\n';
        }
    } else {
        for (int i = 0; i < n; ++i) {
            vector<ll> ppf = dfs_(i, -1);
            if (k >= ppf.size())
                cout << ppf.back() << '\n';
            else
                cout << ppf[k] << '\n';
        }

    }
}

Compilation message

Main.cpp: In function 'std::vector<long long int> dfs_(int, int)':
Main.cpp:25:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   25 |     if (edg[v].empty() || edg[v].size() == 1 && edg[v][0].first == rt) {
      |                           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:94:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   94 |     if (edg[v].empty() || edg[v].size() == 1 && edg[v][0].first == rt) {
      |                           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:168:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |             if (k >= ppf.size())
      |                 ~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 8 ms 2692 KB Output is correct
4 Correct 8 ms 2636 KB Output is correct
5 Correct 10 ms 2708 KB Output is correct
6 Correct 8 ms 2668 KB Output is correct
7 Correct 7 ms 2680 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 8 ms 2692 KB Output is correct
4 Correct 8 ms 2636 KB Output is correct
5 Correct 10 ms 2708 KB Output is correct
6 Correct 8 ms 2668 KB Output is correct
7 Correct 7 ms 2680 KB Output is correct
8 Correct 294 ms 2876 KB Output is correct
9 Correct 317 ms 3084 KB Output is correct
10 Correct 108 ms 2756 KB Output is correct
11 Correct 403 ms 2792 KB Output is correct
12 Correct 148 ms 2764 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 8 ms 2692 KB Output is correct
4 Correct 8 ms 2636 KB Output is correct
5 Correct 10 ms 2708 KB Output is correct
6 Correct 8 ms 2668 KB Output is correct
7 Correct 7 ms 2680 KB Output is correct
8 Correct 294 ms 2876 KB Output is correct
9 Correct 317 ms 3084 KB Output is correct
10 Correct 108 ms 2756 KB Output is correct
11 Correct 403 ms 2792 KB Output is correct
12 Correct 148 ms 2764 KB Output is correct
13 Execution timed out 1088 ms 2980 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 10484 KB Output is correct
2 Correct 171 ms 16676 KB Output is correct
3 Correct 131 ms 10296 KB Output is correct
4 Correct 149 ms 10448 KB Output is correct
5 Correct 159 ms 12712 KB Output is correct
6 Correct 133 ms 10296 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 8 ms 2692 KB Output is correct
4 Correct 8 ms 2636 KB Output is correct
5 Correct 10 ms 2708 KB Output is correct
6 Correct 8 ms 2668 KB Output is correct
7 Correct 7 ms 2680 KB Output is correct
8 Correct 294 ms 2876 KB Output is correct
9 Correct 317 ms 3084 KB Output is correct
10 Correct 108 ms 2756 KB Output is correct
11 Correct 403 ms 2792 KB Output is correct
12 Correct 148 ms 2764 KB Output is correct
13 Execution timed out 1088 ms 2980 KB Time limit exceeded
14 Halted 0 ms 0 KB -