oj.uz

Submission #786238

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

using namespace std;

typedef long long ll;

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

void dfs(int x, int p=-1){
    if((int)link[x].size() - int(p!=-1) == 0){
        vec[x].push_back(0);
        return;
    }
    for(auto y: link[x]){
        if(y.first==p) continue;
        dfs(y.first, x);
        assert(!vec[y.first].empty());
        vec[y.first][0] += y.second;
        vector<ll> newVec;
        int a = 0, b = 0;
        while((int)newVec.size() < k && !(a==(int)vec[x].size() && b==(int)vec[y.first].size())){
            if(a == (int)vec[x].size() || (b != (int)vec[y.first].size() && vec[x][a] < vec[y.first][b]))
                newVec.push_back(vec[y.first][b++]);
            else newVec.push_back(vec[x][a++]);
        }
        vec[x].swap(newVec);
    }
//    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++) vec[j].clear();
        dfs(i);
        ll sum = 0;
        for(auto x: vec[i]) sum+=x;
        printf("%lld\n", sum);
    }
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 5 ms 4948 KB Output is correct
4 Correct 7 ms 4948 KB Output is correct
5 Correct 7 ms 4948 KB Output is correct
6 Correct 6 ms 5028 KB Output is correct
7 Correct 6 ms 5004 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 5 ms 4948 KB Output is correct
4 Correct 7 ms 4948 KB Output is correct
5 Correct 7 ms 4948 KB Output is correct
6 Correct 6 ms 5028 KB Output is correct
7 Correct 6 ms 5004 KB Output is correct
8 Correct 111 ms 5644 KB Output is correct
9 Correct 238 ms 5484 KB Output is correct
10 Correct 79 ms 5208 KB Output is correct
11 Correct 216 ms 5672 KB Output is correct
12 Correct 84 ms 5324 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 5 ms 4948 KB Output is correct
4 Correct 7 ms 4948 KB Output is correct
5 Correct 7 ms 4948 KB Output is correct
6 Correct 6 ms 5028 KB Output is correct
7 Correct 6 ms 5004 KB Output is correct
8 Correct 111 ms 5644 KB Output is correct
9 Correct 238 ms 5484 KB Output is correct
10 Correct 79 ms 5208 KB Output is correct
11 Correct 216 ms 5672 KB Output is correct
12 Correct 84 ms 5324 KB Output is correct
13 Execution timed out 630 ms 13640 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 13244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 5 ms 4948 KB Output is correct
4 Correct 7 ms 4948 KB Output is correct
5 Correct 7 ms 4948 KB Output is correct
6 Correct 6 ms 5028 KB Output is correct
7 Correct 6 ms 5004 KB Output is correct
8 Correct 111 ms 5644 KB Output is correct
9 Correct 238 ms 5484 KB Output is correct
10 Correct 79 ms 5208 KB Output is correct
11 Correct 216 ms 5672 KB Output is correct
12 Correct 84 ms 5324 KB Output is correct
13 Execution timed out 630 ms 13640 KB Time limit exceeded
14 Halted 0 ms 0 KB -