oj.uz

Submission #537464

# Submission time Handle Problem Language Result Execution time Memory
537464 2022-03-15T06:32:09 Z maomao90 Paths (RMI21_paths) C++17
56 / 100
 600 ms 60648 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));
    }
    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 5 ms 5716 KB Output is correct
2 Correct 3 ms 5804 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5716 KB Output is correct
2 Correct 3 ms 5804 KB Output is correct
3 Correct 7 ms 5932 KB Output is correct
4 Correct 8 ms 5844 KB Output is correct
5 Correct 9 ms 5952 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 7 ms 5844 KB Output is correct
8 Correct 119 ms 8792 KB Output is correct
9 Correct 109 ms 8820 KB Output is correct
10 Correct 51 ms 6552 KB Output is correct
11 Correct 92 ms 11948 KB Output is correct
12 Correct 82 ms 7244 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5716 KB Output is correct
2 Correct 3 ms 5804 KB Output is correct
3 Correct 7 ms 5932 KB Output is correct
4 Correct 8 ms 5844 KB Output is correct
5 Correct 9 ms 5952 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 7 ms 5844 KB Output is correct
8 Correct 119 ms 8792 KB Output is correct
9 Correct 109 ms 8820 KB Output is correct
10 Correct 51 ms 6552 KB Output is correct
11 Correct 92 ms 11948 KB Output is correct
12 Correct 82 ms 7244 KB Output is correct
13 Correct 558 ms 23224 KB Output is correct
14 Correct 464 ms 17900 KB Output is correct
15 Correct 210 ms 7544 KB Output is correct
16 Correct 430 ms 27252 KB Output is correct
17 Correct 330 ms 11796 KB Output is correct
18 Correct 290 ms 14992 KB Output is correct
19 Correct 577 ms 17360 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5716 KB Output is correct
2 Correct 3 ms 5804 KB Output is correct
3 Correct 7 ms 5932 KB Output is correct
4 Correct 8 ms 5844 KB Output is correct
5 Correct 9 ms 5952 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 7 ms 5844 KB Output is correct
8 Correct 119 ms 8792 KB Output is correct
9 Correct 109 ms 8820 KB Output is correct
10 Correct 51 ms 6552 KB Output is correct
11 Correct 92 ms 11948 KB Output is correct
12 Correct 82 ms 7244 KB Output is correct
13 Correct 558 ms 23224 KB Output is correct
14 Correct 464 ms 17900 KB Output is correct
15 Correct 210 ms 7544 KB Output is correct
16 Correct 430 ms 27252 KB Output is correct
17 Correct 330 ms 11796 KB Output is correct
18 Correct 290 ms 14992 KB Output is correct
19 Correct 577 ms 17360 KB Output is correct
20 Execution timed out 1084 ms 60648 KB Time limit exceeded
21 Halted 0 ms 0 KB -