oj.uz

Submission #537470

# Submission time Handle Problem Language Result Execution time Memory
537470 2022-03-15T06:35:11 Z maomao90 Paths (RMI21_paths) C++17
36 / 100
 600 ms 13504 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];

multiset<ll, greater<ll>> dp[MAXN];
void dfs(int u, int p) {
    dp[u].clear();
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        ll x = *dp[v].begin(); dp[v].erase(dp[v].begin());
        dp[v].insert(x + w);
        if (dp[u].size() < dp[v].size()) {
            swap(dp[u], dp[v]);
        }
        for (ll x : dp[v]) {
            dp[u].insert(x);
        }
        while (dp[u].size() > k) {
            dp[u].erase(prev(dp[u].end()));
        }
    }
    if (dp[u].empty()) {
        dp[u].insert(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;
        for (ll x : dp[i]) {
            ans += x;
        }
        cout << ans << '\n';
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:55:29: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |         while (dp[u].size() > k) {
      |                ~~~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:77:13: warning: unused variable 'tk' [-Wunused-variable]
   77 |         int tk = k;
      |             ^~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 11 ms 7380 KB Output is correct
4 Correct 10 ms 7380 KB Output is correct
5 Correct 10 ms 7384 KB Output is correct
6 Correct 9 ms 7380 KB Output is correct
7 Correct 10 ms 7392 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 11 ms 7380 KB Output is correct
4 Correct 10 ms 7380 KB Output is correct
5 Correct 10 ms 7384 KB Output is correct
6 Correct 9 ms 7380 KB Output is correct
7 Correct 10 ms 7392 KB Output is correct
8 Correct 217 ms 7476 KB Output is correct
9 Correct 119 ms 7500 KB Output is correct
10 Correct 109 ms 7428 KB Output is correct
11 Correct 153 ms 7444 KB Output is correct
12 Correct 122 ms 7440 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 11 ms 7380 KB Output is correct
4 Correct 10 ms 7380 KB Output is correct
5 Correct 10 ms 7384 KB Output is correct
6 Correct 9 ms 7380 KB Output is correct
7 Correct 10 ms 7392 KB Output is correct
8 Correct 217 ms 7476 KB Output is correct
9 Correct 119 ms 7500 KB Output is correct
10 Correct 109 ms 7428 KB Output is correct
11 Correct 153 ms 7444 KB Output is correct
12 Correct 122 ms 7440 KB Output is correct
13 Execution timed out 1008 ms 7684 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 13504 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 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 11 ms 7380 KB Output is correct
4 Correct 10 ms 7380 KB Output is correct
5 Correct 10 ms 7384 KB Output is correct
6 Correct 9 ms 7380 KB Output is correct
7 Correct 10 ms 7392 KB Output is correct
8 Correct 217 ms 7476 KB Output is correct
9 Correct 119 ms 7500 KB Output is correct
10 Correct 109 ms 7428 KB Output is correct
11 Correct 153 ms 7444 KB Output is correct
12 Correct 122 ms 7440 KB Output is correct
13 Execution timed out 1008 ms 7684 KB Time limit exceeded
14 Halted 0 ms 0 KB -