oj.uz

Submission #537475

# Submission time Handle Problem Language Result Execution time Memory
537475 2022-03-15T06:48:44 Z maomao90 Paths (RMI21_paths) C++17
68 / 100
 592 ms 27172 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 100005

int n, k;
vii adj[MAXN];

priority_queue<ll> dp[MAXN];
void dfs(int u, int p) {
    while (!dp[u].empty()) {
        dp[u].pop();
    }
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        ll x = dp[v].top(); dp[v].pop();
        dp[v].push(x + w);
        if (dp[u].size() < dp[v].size()) {
            swap(dp[u], dp[v]);
        }
        while (!dp[v].empty()) {
            ll x = dp[v].top(); dp[v].pop();
            dp[u].push(x);
        }
    }
    if (dp[u].empty()) {
        dp[u].push(0);
    }
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> k;
    REP (i, 1, n) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].pb(MP(b, c));
        adj[b].pb(MP(a, c));
    }
    if (k == 1) {
        vll dist(n + 1, 0);
        vll ans(n + 1, 0);
        auto dfs = [&] (auto &&self, int u, int p) {
            if (0) return -1;
            int mx = u;
            for (auto [v, w] : adj[u]) {
                if (v == p) continue;
                dist[v] = dist[u] + w;
                int x = self(self, v, u);
                if (dist[mx] < dist[x]) {
                    mx = x;
                }
            }
            return mx;
        };
        dist[1] = 0;
        int a = dfs(dfs, 1, -1);
        dist[a] = 0;
        int b = dfs(dfs, a, -1);
        REP (i, 1, n + 1) {
            mxto(ans[i], dist[i]);
        }
        dist[b] = 0;
        dfs(dfs, b, -1);
        REP (i, 1, n + 1) {
            mxto(ans[i], dist[i]);
        }
        REP (i, 1, n + 1) {
            cout << ans[i] << '\n';
        }
        return 0;
    }
    REP (i, 1, (n > 2000 ? 2 : (n + 1))) {
        dfs(i, -1);
        ll ans = 0;
        int tk = k;
        while (!dp[i].empty() && tk--) {
            ll x = dp[i].top(); dp[i].pop();
            ans += x;
        }
        cout << ans << '\n';
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 6 ms 5844 KB Output is correct
4 Correct 6 ms 5972 KB Output is correct
5 Correct 7 ms 5844 KB Output is correct
6 Correct 6 ms 5844 KB Output is correct
7 Correct 6 ms 5844 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 6 ms 5844 KB Output is correct
4 Correct 6 ms 5972 KB Output is correct
5 Correct 7 ms 5844 KB Output is correct
6 Correct 6 ms 5844 KB Output is correct
7 Correct 6 ms 5844 KB Output is correct
8 Correct 107 ms 8740 KB Output is correct
9 Correct 94 ms 8832 KB Output is correct
10 Correct 51 ms 6532 KB Output is correct
11 Correct 104 ms 12024 KB Output is correct
12 Correct 56 ms 7256 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 6 ms 5844 KB Output is correct
4 Correct 6 ms 5972 KB Output is correct
5 Correct 7 ms 5844 KB Output is correct
6 Correct 6 ms 5844 KB Output is correct
7 Correct 6 ms 5844 KB Output is correct
8 Correct 107 ms 8740 KB Output is correct
9 Correct 94 ms 8832 KB Output is correct
10 Correct 51 ms 6532 KB Output is correct
11 Correct 104 ms 12024 KB Output is correct
12 Correct 56 ms 7256 KB Output is correct
13 Correct 592 ms 23204 KB Output is correct
14 Correct 400 ms 18012 KB Output is correct
15 Correct 208 ms 7572 KB Output is correct
16 Correct 357 ms 27172 KB Output is correct
17 Correct 318 ms 11928 KB Output is correct
18 Correct 233 ms 15020 KB Output is correct
19 Correct 538 ms 17424 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 12200 KB Output is correct
2 Correct 90 ms 13360 KB Output is correct
3 Correct 69 ms 11768 KB Output is correct
4 Correct 96 ms 12172 KB Output is correct
5 Correct 76 ms 12940 KB Output is correct
6 Correct 75 ms 12080 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 6 ms 5844 KB Output is correct
4 Correct 6 ms 5972 KB Output is correct
5 Correct 7 ms 5844 KB Output is correct
6 Correct 6 ms 5844 KB Output is correct
7 Correct 6 ms 5844 KB Output is correct
8 Correct 107 ms 8740 KB Output is correct
9 Correct 94 ms 8832 KB Output is correct
10 Correct 51 ms 6532 KB Output is correct
11 Correct 104 ms 12024 KB Output is correct
12 Correct 56 ms 7256 KB Output is correct
13 Correct 592 ms 23204 KB Output is correct
14 Correct 400 ms 18012 KB Output is correct
15 Correct 208 ms 7572 KB Output is correct
16 Correct 357 ms 27172 KB Output is correct
17 Correct 318 ms 11928 KB Output is correct
18 Correct 233 ms 15020 KB Output is correct
19 Correct 538 ms 17424 KB Output is correct
20 Correct 87 ms 12200 KB Output is correct
21 Correct 90 ms 13360 KB Output is correct
22 Correct 69 ms 11768 KB Output is correct
23 Correct 96 ms 12172 KB Output is correct
24 Correct 76 ms 12940 KB Output is correct
25 Correct 75 ms 12080 KB Output is correct
26 Incorrect 110 ms 13232 KB Output isn't correct
27 Halted 0 ms 0 KB -