Submission #598494

#	Time	Username	Problem	Language	Result	Execution time	Memory
598494		CaroLinda	Paths (RMI21_paths)	C++14	56 / 100	16 ms	2856 KiB

Main

#include <bits/stdc++.h>

//testing the quadratic

#define ll long long

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

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];
vector<ll> realVec;
vector<int> e, d;
vector<int> qtd;
vector<ll> soma;

int create(){
    e.push_back(0);
    d.push_back(0);
    qtd.push_back(0);
    soma.push_back(0);

    return e.size() - 1;
}

ll m(ll l, ll r){
    return (l+r)>>1LL;
}

void upd(int pos, ll l, ll r, ll id, int toSum){
    if(l == r){
        qtd[pos] += toSum;
        soma[pos] += l * toSum;
        return;
    }

    int aux;

    if(id <= m(l,r)){
        if(!e[pos]){
            aux = create();
            e[pos] = aux;
        }
        upd(e[pos],l,m(l,r), id, toSum);
    }
    else{
        if(!d[pos]){
            aux = create();
            d[pos] = aux;
        }
        upd(d[pos],m(l,r)+1, r, id, toSum);
    }

    soma[pos] = soma[e[pos]]+soma[d[pos]];
    qtd[pos] = qtd[e[pos]]+qtd[d[pos]];
}

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]){
            upd(1,0, MAX_VAL, mx[x], 1);
            mx[x] = curVal;
        }
        else upd(1,0,MAX_VAL, curVal, 1);
    }

    return mx[x];
}

ll getAnswer(int pos, ll l, ll r, int k){
    if(!k || !pos)
        return 0;

    if(qtd[pos] <= k)
        return soma[pos];

    if(l == r){
        return l * k;
    }

    if(qtd[d[pos]] >= k)
        return getAnswer(d[pos],m(l,r)+1, r, k);

    return getAnswer(e[pos], l, m(l,r), k-qtd[d[pos]])+soma[d[pos]];
}

void printSeg(int pos, ll l, ll r){
    if(!qtd[pos] || !pos)
        return;

    if(l == r)
        return (void)(cout << l << " " << qtd[pos]);

    printSeg(e[pos],l,m(l,r));
    printSeg(d[pos],m(l,r)+1, r);
}

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] = getAnswer(1,0,MAX_VAL,K);

    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]);

        upd(1,0,MAX_VAL, novoMaior, -1);
        upd(1,0,MAX_VAL, novoMaior+edgWeight, 1);
        upd(1,0,MAX_VAL, mx[viz]+edgWeight, -1);
        upd(1,0,MAX_VAL, mx[viz], 1);

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

        dfsReroot(viz, x);

        mx[viz] = savemx;

        upd(1,0,MAX_VAL, novoMaior, 1);
        upd(1,0,MAX_VAL, novoMaior+edgWeight, -1);
        upd(1,0,MAX_VAL, mx[viz]+edgWeight, 1);
        upd(1,0,MAX_VAL, mx[viz], -1);
    }
}

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));
    }

    create();
    create();

    dfs(1);
    upd(1,0,MAX_VAL, mx[1],1);
    dfsReroot(1,-1);

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

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