Submission #523295

#	Time	Username	Problem	Language	Result	Execution time	Memory
523295		wdjpng	Paths (RMI21_paths)	C++17	0 / 100	417 ms	23596 KiB

Main

#ifndef LOCAL
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i =0; i<n;i++)
#define all(a) a.begin(), a.end()

using namespace std;

int k;
struct edge{
    int c, w;
};

struct topkmultiset : multiset<int> {
    int k;
    multiset<int>::iterator it;
    topkmultiset(int k) : k(k) { }
    int sum_topk() {}
    int replace(int a, int b) {}
};

vector<int>best_of_subtree;
multiset<int> dfs(int v, int p, vector<vector<edge>>& E)
{
    multiset<int> cs;
    cs.insert(0);

    for(edge e : E[v])
    {
        if(e.w==p) continue;
        multiset<int> ns = dfs(e.w, v, E);

        auto it = ns.end();
        it--;
        int tmp = *it;
        ns.erase(it);
        ns.insert(tmp+e.c);
        best_of_subtree[e.w]=tmp;

        if(cs.size()<ns.size()) swap(cs, ns);
        for(int x : ns) cs.insert(x);
    }
    
    // while (cs.size()>k+3) cs.erase(cs.begin()); 
    
    return cs;
}

int c = 0;
void multiset_replace(multiset<pair<int, int>>::iterator& it, int old, int next, int& sum, multiset<pair<int, int>>&ms)
{
    auto low = ms.lower_bound(make_pair(old, 0));
    if(old <it->first) 
    {
        ms.erase(low);
    } else {
        it--; 
        sum+=(*(it)).first-old;
        if(it==low) --it;
        ms.erase(low);
    }

    if(next<(*it).first) 
    {
        ms.insert(make_pair(next, ++c));
    } else {
        ms.insert(make_pair(next, ++c));
        sum+=next-(*(it)).first;
        it++; 
    }
}

vector<int>sol;
void meta_dfs(int v, int p, multiset<pair<int, int>>&ms, vector<vector<edge>>& E, multiset<pair<int, int>>::iterator& it, int& sum)
{
    sol[v]=sum;
    for(edge e : E[v])
    {
        if(e.w==p) continue;

        // replace biggest link to child
        multiset_replace(it, best_of_subtree[e.w]+e.c, best_of_subtree[e.w], sum, ms);
        
        // add child weight to bigggest link 
        auto best_it = (ms.rbegin());
        if (best_it->first==best_of_subtree[e.w])
            ++best_it;
        int best = best_it->first;
        multiset_replace(it, best, best+e.c, sum, ms);

        // remove child weight from biggest link
        multiset_replace(it, best+e.c, best, sum, ms);

        // place biggest link to child in again
        multiset_replace(it, best_of_subtree[e.w], best_of_subtree[e.w]+e.c, sum, ms);

        meta_dfs(e.w,v,ms,E,it,sum);
    }
}


signed main()
{
    int n;
    cin>>n>>k;
    
    best_of_subtree.assign(n+1, -1);
    vector<vector<edge>>E(n+1);
    rep(i, n-1)
    {
        int a, b, c;
        cin>>a>>b>>c;

        E[a].push_back({c,b});
        E[b].push_back({c,a});
    }

    sol.resize(n+1);
    multiset<int>s  = dfs(1, -1, E);
    multiset<pair<int, int>>ms;
    auto it2 = s.begin();
    rep(i, s.size())
    {
        ms.insert(make_pair(*it2, 0));
        it2++;
    }

    int sum = 0;
    while (ms.size()-4<k)  ms.insert({0,0});
    
    auto it = ms.end(); 
    for(int j = 0; j < k && j < s.size(); j++)
    {
        it--;
        sum+=(*it).first;
    }

    meta_dfs(1, -1, ms, E, it, sum);
    for(int i = 1;i <= n; i++) cout<<sol[i]<<"\n";
}

Compilation message (stderr)

Main.cpp: In member function 'long long int topkmultiset::sum_topk()':
Main.cpp:23:21: warning: no return statement in function returning non-void [-Wreturn-type]
   23 |     int sum_topk() {}
      |                     ^
Main.cpp: In member function 'long long int topkmultiset::replace(long long int, long long int)':
Main.cpp:24:32: warning: no return statement in function returning non-void [-Wreturn-type]
   24 |     int replace(int a, int b) {}
      |                                ^
Main.cpp: In function 'int main()':
Main.cpp:9:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(i,n) for(int i =0; i<n;i++)
......
  127 |     rep(i, s.size())
      |         ~~~~~~~~~~~              
Main.cpp:127:5: note: in expansion of macro 'rep'
  127 |     rep(i, s.size())
      |     ^~~
Main.cpp:134:23: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  134 |     while (ms.size()-4<k)  ms.insert({0,0});
      |            ~~~~~~~~~~~^~
Main.cpp:137:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(int j = 0; j < k && j < s.size(); j++)
      |                             ~~^~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32