oj.uz

Submission #539443

# Submission time Handle Problem Language Result Execution time Memory
539443 2022-03-18T23:22:53 Z doowey Paths (RMI21_paths) C++14
12 / 100
 72 ms 17764 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
vector<pii> T[N];
int par[N];
set<pll> W[N];

void dfs0(int u, int p){
    par[u] = p;
    bool leaf = true;
    pll A;
    for(auto x : T[u]){
        if(x.fi != p){
            leaf = false;
            dfs0(x.fi, u);
            auto it = W[x.fi].end();
            it -- ;
            A = *it;
            A.fi += x.se;
            W[x.fi].erase(it);
            W[x.fi].insert(A);
            if(W[x.fi].size() > W[u].size()){
                swap(W[x.fi], W[u]);
            }
            for(auto y : W[x.fi]){
                W[u].insert(y);
            }
            W[x.fi].clear();
        }
    }
    if(leaf) W[u].insert(mp(0ll, u));
}

ll soln[N];
int mark[N];
ll mx[N];

ll sol;
ll ext;

vector<int> ss;

void dfs1(int u, int pa){
    for(auto x : T[u]){
        if(x.fi == pa) continue;
        dfs1(x.fi, u);
        mark[u] += mark[x.fi];
    }
    if(mark[u] > 0){
        soln[u] = sol;
    }
}

void dfs2(int u, int pa, ll non){
    ll f;
    ext = max(ext, non);
    if(mark[u] == 0) soln[u] = max(soln[u], sol + non);
    for(auto x : T[u]){
        if(x.fi == pa) continue;
        f = non;
        if(mark[x.fi] == 0) f += x.se;
        dfs2(x.fi, u, f);
    }
}

ll pat[N];

void dfsk(int u, int pa){
    for(auto x : T[u]){
        if(x.fi == pa) continue;
        dfsk(x.fi, u);
        pat[u] = max(pat[u], pat[x.fi] + x.se);
    }
}

void solve(int u, int pa, ll ext){
    pll ai = mp(0, -1);
    pll bi = mp(0, -1);
    pll S;

    for(auto x : T[u]){
        if(x.fi == pa) continue;
        S.fi = pat[x.fi] + x.se;
        S.se = x.fi;
        if(S > ai){
            bi = ai;
            ai = S;
        }
        else if(S > bi){
            bi = S;
        }
    }
    ll nw;
    for(auto x : T[u]){
        if(x.fi == pa) continue;
        nw = ext;
        if(ai.se == x.fi) nw = max(nw, bi.fi);
        else nw = max(nw, ai.fi);
        nw += x.se;
        solve(x.fi, u, nw);
    }
    soln[u] = max(pat[u], ext);

}

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);

    int n, k;
    cin >> n >> k;
    int u, v, w;
    for(int i = 1; i < n; i ++ ){
        cin >> u >> v >> w;
        T[u].push_back(mp(v, w));
        T[v].push_back(mp(u, w));
    }
    // k == 1 special case
    if(k == 1){
        dfsk(1, -1);
        solve(1, -1, 0);
        for(int i = 1; i <= n; i ++ ){
            cout << soln[i] << "\n";
        }
        return 0;
    }
    dfs0(1, -1);
    auto it = W[1].end();
    for(int i = 0 ; i < k ; i ++ ){
        if(it == W[1].begin()) break;
        it -- ;
        sol += it->fi;
        mark[it->se] = 1;
        ss.push_back(it->se);
    }
    soln[1]=sol;
    dfs1(1, -1);
    dfs2(1, -1, 0);
    for(auto x : ss){
        soln[x] = max(soln[x], sol + ext);
    }
    for(int i = 1; i <= n; i ++ ){
        cout << soln[i] << "\n";
    }
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Incorrect 3 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Incorrect 3 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Incorrect 3 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Incorrect 3 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 13732 KB Output is correct
2 Correct 72 ms 17764 KB Output is correct
3 Correct 56 ms 15436 KB Output is correct
4 Correct 61 ms 15772 KB Output is correct
5 Correct 64 ms 16632 KB Output is correct
6 Correct 58 ms 15828 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Incorrect 3 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -