oj.uz

Submission #598503

# Submission time Handle Problem Language Result Execution time Memory
598503 2022-07-18T12:19:20 Z CaroLinda Paths (RMI21_paths) C++14
100 / 100
 334 ms 26580 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2724 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2724 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 4 ms 2732 KB Output is correct
9 Correct 5 ms 2900 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 3 ms 2844 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2724 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 4 ms 2732 KB Output is correct
9 Correct 5 ms 2900 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 3 ms 2844 KB Output is correct
13 Correct 5 ms 2900 KB Output is correct
14 Correct 5 ms 3196 KB Output is correct
15 Correct 7 ms 3040 KB Output is correct
16 Correct 5 ms 2996 KB Output is correct
17 Correct 5 ms 2900 KB Output is correct
18 Correct 4 ms 2900 KB Output is correct
19 Correct 5 ms 2968 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 17064 KB Output is correct
2 Correct 280 ms 24312 KB Output is correct
3 Correct 204 ms 19092 KB Output is correct
4 Correct 263 ms 19352 KB Output is correct
5 Correct 296 ms 21168 KB Output is correct
6 Correct 281 ms 19448 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2724 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 4 ms 2732 KB Output is correct
9 Correct 5 ms 2900 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 3 ms 2844 KB Output is correct
13 Correct 5 ms 2900 KB Output is correct
14 Correct 5 ms 3196 KB Output is correct
15 Correct 7 ms 3040 KB Output is correct
16 Correct 5 ms 2996 KB Output is correct
17 Correct 5 ms 2900 KB Output is correct
18 Correct 4 ms 2900 KB Output is correct
19 Correct 5 ms 2968 KB Output is correct
20 Correct 282 ms 17064 KB Output is correct
21 Correct 280 ms 24312 KB Output is correct
22 Correct 204 ms 19092 KB Output is correct
23 Correct 263 ms 19352 KB Output is correct
24 Correct 296 ms 21168 KB Output is correct
25 Correct 281 ms 19448 KB Output is correct
26 Correct 324 ms 19576 KB Output is correct
27 Correct 319 ms 24228 KB Output is correct
28 Correct 334 ms 25280 KB Output is correct
29 Correct 230 ms 19296 KB Output is correct
30 Correct 329 ms 19744 KB Output is correct
31 Correct 320 ms 18900 KB Output is correct
32 Correct 317 ms 21712 KB Output is correct
33 Correct 327 ms 19592 KB Output is correct
34 Correct 208 ms 19408 KB Output is correct
35 Correct 310 ms 19764 KB Output is correct
36 Correct 302 ms 26580 KB Output is correct