oj.uz

Submission #537570

# Submission time Handle Problem Language Result Execution time Memory
537570 2022-03-15T08:49:56 Z tqbfjotld Paths (RMI21_paths) C++14
36 / 100
 600 ms 202228 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int K;

vector<int> memo[2005][2005];
vector<pair<int,int> > adjl[2005];

vector<int> dfs(int node, int pa){
    if (!memo[node][pa].empty()) return memo[node][pa];
    vector<int> cur;
    cur.push_back(0);
    for (auto x : adjl[node]){
        if (x.first==pa) continue;
        auto res = dfs(x.first,node);
        res[0] += x.second;
        vector<int> nw;
        int a = 0,b=0;
        while (nw.size()<K && (a<cur.size()) || (b<res.size())){
            if (a==cur.size()){
                nw.push_back(res[b]);b++;
            }
            else if (b==res.size()){
                nw.push_back(cur[a]); a++;
            }
            else if (cur[a]>res[b]){
                nw.push_back(cur[a]); a++;
            }
            else {
                nw.push_back(res[b]); b++;
            }
        }
        swap(cur,nw);
    }
    return memo[node][pa] = cur;
}

main(){
    int n;
    scanf("%lld%lld",&n,&K);
    for (int x = 0; x<n-1; x++){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        adjl[a].push_back({b,c});
        adjl[b].push_back({a,c});
    }
    for (int x = 1; x<=n; x++){
        auto res = dfs(x,0);
        int ans = 0;
        for (int y = 0; y<min(K,(int)res.size()); y++){
            ans += res[y];
        }
        printf("%lld\n",ans);
    }
}

Compilation message

Main.cpp: In function 'std::vector<long long int> dfs(long long int, long long int)':
Main.cpp:20:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   20 |         while (nw.size()<K && (a<cur.size()) || (b<res.size())){
      |                ~~~~~~~~~^~
Main.cpp:20:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         while (nw.size()<K && (a<cur.size()) || (b<res.size())){
      |                                ~^~~~~~~~~~~
Main.cpp:20:51: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         while (nw.size()<K && (a<cur.size()) || (b<res.size())){
      |                                                  ~^~~~~~~~~~~
Main.cpp:20:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   20 |         while (nw.size()<K && (a<cur.size()) || (b<res.size())){
      |                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:21:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             if (a==cur.size()){
      |                 ~^~~~~~~~~~~~
Main.cpp:24:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             else if (b==res.size()){
      |                      ~^~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main(){
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%lld%lld",&n,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94668 KB Output is correct
2 Correct 59 ms 94708 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94668 KB Output is correct
2 Correct 59 ms 94708 KB Output is correct
3 Correct 52 ms 94896 KB Output is correct
4 Correct 51 ms 94796 KB Output is correct
5 Correct 51 ms 94880 KB Output is correct
6 Correct 46 ms 94780 KB Output is correct
7 Correct 51 ms 94896 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94668 KB Output is correct
2 Correct 59 ms 94708 KB Output is correct
3 Correct 52 ms 94896 KB Output is correct
4 Correct 51 ms 94796 KB Output is correct
5 Correct 51 ms 94880 KB Output is correct
6 Correct 46 ms 94780 KB Output is correct
7 Correct 51 ms 94896 KB Output is correct
8 Correct 59 ms 98920 KB Output is correct
9 Correct 53 ms 96272 KB Output is correct
10 Correct 53 ms 96716 KB Output is correct
11 Correct 203 ms 96436 KB Output is correct
12 Correct 56 ms 97812 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94668 KB Output is correct
2 Correct 59 ms 94708 KB Output is correct
3 Correct 52 ms 94896 KB Output is correct
4 Correct 51 ms 94796 KB Output is correct
5 Correct 51 ms 94880 KB Output is correct
6 Correct 46 ms 94780 KB Output is correct
7 Correct 51 ms 94896 KB Output is correct
8 Correct 59 ms 98920 KB Output is correct
9 Correct 53 ms 96272 KB Output is correct
10 Correct 53 ms 96716 KB Output is correct
11 Correct 203 ms 96436 KB Output is correct
12 Correct 56 ms 97812 KB Output is correct
13 Correct 91 ms 119396 KB Output is correct
14 Correct 69 ms 102744 KB Output is correct
15 Correct 59 ms 99276 KB Output is correct
16 Execution timed out 1089 ms 105384 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 198 ms 202228 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94668 KB Output is correct
2 Correct 59 ms 94708 KB Output is correct
3 Correct 52 ms 94896 KB Output is correct
4 Correct 51 ms 94796 KB Output is correct
5 Correct 51 ms 94880 KB Output is correct
6 Correct 46 ms 94780 KB Output is correct
7 Correct 51 ms 94896 KB Output is correct
8 Correct 59 ms 98920 KB Output is correct
9 Correct 53 ms 96272 KB Output is correct
10 Correct 53 ms 96716 KB Output is correct
11 Correct 203 ms 96436 KB Output is correct
12 Correct 56 ms 97812 KB Output is correct
13 Correct 91 ms 119396 KB Output is correct
14 Correct 69 ms 102744 KB Output is correct
15 Correct 59 ms 99276 KB Output is correct
16 Execution timed out 1089 ms 105384 KB Time limit exceeded
17 Halted 0 ms 0 KB -