oj.uz

Submission #537473

# Submission time Handle Problem Language Result Execution time Memory
537473 2022-03-15T06:41:54 Z maomao90 Paths (RMI21_paths) C++17
68 / 100
 600 ms 63592 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 + 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 5716 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 8 ms 5844 KB Output is correct
4 Correct 6 ms 5960 KB Output is correct
5 Correct 8 ms 5844 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 5 ms 5844 KB Output is correct
8 Correct 105 ms 8784 KB Output is correct
9 Correct 93 ms 8908 KB Output is correct
10 Correct 55 ms 6576 KB Output is correct
11 Correct 102 ms 11968 KB Output is correct
12 Correct 59 ms 7252 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 8 ms 5844 KB Output is correct
4 Correct 6 ms 5960 KB Output is correct
5 Correct 8 ms 5844 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 5 ms 5844 KB Output is correct
8 Correct 105 ms 8784 KB Output is correct
9 Correct 93 ms 8908 KB Output is correct
10 Correct 55 ms 6576 KB Output is correct
11 Correct 102 ms 11968 KB Output is correct
12 Correct 59 ms 7252 KB Output is correct
13 Correct 567 ms 23180 KB Output is correct
14 Correct 437 ms 17904 KB Output is correct
15 Correct 196 ms 7448 KB Output is correct
16 Correct 386 ms 27220 KB Output is correct
17 Correct 306 ms 11804 KB Output is correct
18 Correct 245 ms 15020 KB Output is correct
19 Correct 539 ms 17388 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 12196 KB Output is correct
2 Correct 95 ms 15364 KB Output is correct
3 Correct 68 ms 13840 KB Output is correct
4 Correct 91 ms 14156 KB Output is correct
5 Correct 78 ms 15012 KB Output is correct
6 Correct 76 ms 14160 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 8 ms 5844 KB Output is correct
4 Correct 6 ms 5960 KB Output is correct
5 Correct 8 ms 5844 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 5 ms 5844 KB Output is correct
8 Correct 105 ms 8784 KB Output is correct
9 Correct 93 ms 8908 KB Output is correct
10 Correct 55 ms 6576 KB Output is correct
11 Correct 102 ms 11968 KB Output is correct
12 Correct 59 ms 7252 KB Output is correct
13 Correct 567 ms 23180 KB Output is correct
14 Correct 437 ms 17904 KB Output is correct
15 Correct 196 ms 7448 KB Output is correct
16 Correct 386 ms 27220 KB Output is correct
17 Correct 306 ms 11804 KB Output is correct
18 Correct 245 ms 15020 KB Output is correct
19 Correct 539 ms 17388 KB Output is correct
20 Correct 81 ms 12196 KB Output is correct
21 Correct 95 ms 15364 KB Output is correct
22 Correct 68 ms 13840 KB Output is correct
23 Correct 91 ms 14156 KB Output is correct
24 Correct 78 ms 15012 KB Output is correct
25 Correct 76 ms 14160 KB Output is correct
26 Execution timed out 1057 ms 63592 KB Time limit exceeded
27 Halted 0 ms 0 KB -