oj.uz

Submission #786251

# Submission time Handle Problem Language Result Execution time Memory
786251 2023-07-18T05:49:43 Z 반딧불(#10026) Paths (RMI21_paths) C++17
36 / 100
 600 ms 12356 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
vector<pair<int, ll> > link[100002];
multiset<ll> mst[100002];

void dfs(int x, int p=-1){
    if((int)link[x].size() - int(p!=-1) == 0){
        mst[x].insert(0);
        return;
    }
    for(auto y: link[x]){
        if(y.first==p) continue;
        dfs(y.first, x);
        assert(!mst[y.first].empty());
        ll tmp = *mst[y.first].rbegin();
        mst[y.first].erase(mst[y.first].find(tmp));
        mst[y.first].insert(tmp+y.second);

        if(mst[y.first].size() > mst[x].size()) mst[x].swap(mst[y.first]);
        for(auto p: mst[y.first]) mst[x].insert(p);
        mst[y.first].clear();
        while((int)mst[x].size() > k) mst[x].erase(mst[x].begin());
    }
//    printf("Parent %d, x %d: ", p, x);
//    for(auto t: st[x]) printf("%lld ", t);
//    puts("");
}

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<n; i++){
        int x, y; ll c;
        scanf("%d %d %lld", &x, &y, &c);
        link[x].push_back(make_pair(y, c));
        link[y].push_back(make_pair(x, c));
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) mst[j].clear();
        dfs(i);
        ll sum = 0;
        while(!mst[i].empty()) sum += *mst[i].begin(), mst[i].erase(mst[i].begin());
        printf("%lld\n", sum);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d %d %lld", &x, &y, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7284 KB Output is correct
3 Correct 7 ms 7252 KB Output is correct
4 Correct 7 ms 7364 KB Output is correct
5 Correct 8 ms 7252 KB Output is correct
6 Correct 6 ms 7368 KB Output is correct
7 Correct 7 ms 7252 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7284 KB Output is correct
3 Correct 7 ms 7252 KB Output is correct
4 Correct 7 ms 7364 KB Output is correct
5 Correct 8 ms 7252 KB Output is correct
6 Correct 6 ms 7368 KB Output is correct
7 Correct 7 ms 7252 KB Output is correct
8 Correct 157 ms 7408 KB Output is correct
9 Correct 98 ms 7488 KB Output is correct
10 Correct 69 ms 7428 KB Output is correct
11 Correct 106 ms 7392 KB Output is correct
12 Correct 100 ms 7412 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7284 KB Output is correct
3 Correct 7 ms 7252 KB Output is correct
4 Correct 7 ms 7364 KB Output is correct
5 Correct 8 ms 7252 KB Output is correct
6 Correct 6 ms 7368 KB Output is correct
7 Correct 7 ms 7252 KB Output is correct
8 Correct 157 ms 7408 KB Output is correct
9 Correct 98 ms 7488 KB Output is correct
10 Correct 69 ms 7428 KB Output is correct
11 Correct 106 ms 7392 KB Output is correct
12 Correct 100 ms 7412 KB Output is correct
13 Execution timed out 789 ms 7644 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 1071 ms 12356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7284 KB Output is correct
3 Correct 7 ms 7252 KB Output is correct
4 Correct 7 ms 7364 KB Output is correct
5 Correct 8 ms 7252 KB Output is correct
6 Correct 6 ms 7368 KB Output is correct
7 Correct 7 ms 7252 KB Output is correct
8 Correct 157 ms 7408 KB Output is correct
9 Correct 98 ms 7488 KB Output is correct
10 Correct 69 ms 7428 KB Output is correct
11 Correct 106 ms 7392 KB Output is correct
12 Correct 100 ms 7412 KB Output is correct
13 Execution timed out 789 ms 7644 KB Time limit exceeded
14 Halted 0 ms 0 KB -