Submission #537574

#	Time	Username	Problem	Language	Result	Execution time	Memory
537574		tqbfjotld	Paths (RMI21_paths)	C++14	36 / 100	1100 ms	27568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

int K;

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

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 (stderr)

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 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32