Submission #598503

#	Time	Username	Problem	Language	Result	Execution time	Memory
598503		CaroLinda	Paths (RMI21_paths)	C++14	100 / 100	334 ms	26580 KiB

Main

#include <bits/stdc++.h>

//testing the quadratic

#define ll long long

const ll MAX_VAL = 1e14+10LL;
const int MAXN = 1e5+10;

using namespace std;

int N, K;
int par[MAXN];
ll prof[MAXN], mx[MAXN], ans[MAXN];
vector<pair<int,ll> > adj[MAXN];
bool used[MAXN];
ll edgParent[MAXN];
multiset<ll> pequenos;
multiset<ll> grandes;
ll curAns;

ll dfs(int x){
    mx[x] = 0;

    for(auto &e: adj[x]){
        if(e.first == par[x])
            continue;

        par[e.first] = x;
        prof[e.first] = prof[x] + e.second;
        edgParent[e.first] = prof[x];

        ll curVal = dfs(e.first)+e.second;

        if(curVal > mx[x]){
            pequenos.insert(mx[x]);
            mx[x] = curVal;
        }
        else pequenos.insert(curVal);
    }

    return mx[x];
}

void apaga(ll val){
    if(grandes.find(val) != grandes.end()){
        curAns -= val;
        grandes.erase(grandes.find(val));
        ll toInsert =*prev(pequenos.end());
        curAns += toInsert;
        grandes.insert(toInsert);
        pequenos.erase(prev(pequenos.end()));
    }
    else{
        pequenos.erase(pequenos.find(val));
    }
}

void insere(ll val){
    curAns += val;
    grandes.insert(val);
    ll toRemove = *grandes.begin();
    curAns -= toRemove;
    grandes.erase(grandes.begin());
    pequenos.insert(toRemove);
}

void dfsReroot(int x, int antigo){
    int n = adj[x].size();

    vector<ll> pref(n+1, 0);
    vector<ll> suf(n+2, 0);

    for(int i = 0; i < n; i++){
        pref[i+1] = max(pref[i], mx[adj[x][i].first]+adj[x][i].second );
    }
    for(int i = n-1; i >= 0; i--){
        suf[i+1] = max(suf[i+2], mx[adj[x][i].first]+adj[x][i].second);
    }

    ans[x] = curAns;

    for(int i = 0; i < n; i++){
        int viz = adj[x][i].first;
        ll edgWeight = adj[x][i].second;

        if(viz == antigo) continue;

        ll novoMaior = max(pref[i], suf[i+2]);

        insere(novoMaior+edgWeight);
        apaga(novoMaior);
        insere(mx[viz]);
        apaga(mx[viz]+edgWeight);

        mx[x] = novoMaior;
        ll savemx = mx[viz];

        dfsReroot(viz, x);

        mx[viz] = savemx;

        insere(novoMaior);
        apaga(novoMaior+edgWeight);
        insere(mx[viz]+edgWeight);
        apaga(mx[viz]);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    for(int i= 1, a, b, c; i < N; i++){
        cin >> a >> b >> c;

        adj[a].push_back(make_pair(b,c));
        adj[b].push_back(make_pair(a,c));
    }


    dfs(1);
    pequenos.insert(mx[1]);
    while(grandes.size() < K){
        auto it = prev(pequenos.end());
        ll val = *it;
        curAns += val;
        pequenos.erase(it);
        grandes.insert(val);
    }
    dfsReroot(1,-1);

    for(int i = 1; i <= N; i++)
        cout << ans[i] << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:125:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |     while(grandes.size() < K){
      |           ~~~~~~~~~~~~~~~^~~

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