oj.uz

Submission #711207

# Submission time Handle Problem Language Result Execution time Memory
711207 2023-03-16T10:01:49 Z TimDee Paths (RMI21_paths) C++17
100 / 100
 498 ms 246748 KB 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,popcnt")

using ll = long long;
//#define int long long
//#define double long double
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<ll,int>
#define f first
#define s second 
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//const int inf = 1e18;
const int mod = 1e9+7;//998244353;

const int N = 1e5;
vector<pi> adj[N];
pi z[N]; int zzz=0;
pi mx[N];
pi out[N];
ll ans[N];

void dfs(int u, int p) {
    mx[u]={-1,-1};
    if (adj[u].size()==1) mx[u]={0,u};
    for (auto&e:adj[u]) {
        int v=e.f, w=e.s;
        if (v==p) continue;
        dfs(v,u);
        if (mx[v].f+w > mx[u].f) {
            if (mx[u].s!=-1) z[zzz++]=mx[u];
            mx[u]={mx[v].f+w,mx[v].s};
        } else {
            z[zzz++]={mx[v].f+w,mx[v].s};
        }
    }
}
void dfs2(int u, int p, pi o) {
    out[u]=o;
    vector<pi> pr={{-1,-1}};
    for(auto&e:adj[u]) {
        int v=e.f, w=e.s;
        if (v==p) {
            pr.pb(pr.back());
            continue;
        }
        if (mx[v].f+w>pr.back().f) pr.pb({mx[v].f+w,mx[v].s});
        else pr.pb(pr.back());
    }
    pi sf={-1,-1};
    int sz=adj[u].size();
    for (int i=sz-1; i>=0; --i) {
        auto e=adj[u][i];
        int v=e.f, w=e.s;
        if (v==p) continue;
        pi x=(pr[i].f > sf.f)?pr[i]:sf;
        if (o.f > x.f) x=o;
        x.f+=w;
        dfs2(v,u,x);
        if (mx[v].f+w > sf.f) sf={mx[v].f+w,mx[v].s};
    }
}

const ll sz=1ll<<47;

struct sgt {
    int l,r;
    int c;
    ll s;
    sgt() {
        l=r=-1;
        c=s=0;
    }
};

const int tsz=9.6e6;
sgt t[tsz];
int nxt=1;

void add(int v, ll l, ll r, ll x) {
    t[v].c++, t[v].s+=x;
    if (r-l==1) return;
    ll m=(l+r)>>1;
    int L=t[v].l, R=t[v].r;
    if (x<m) {
        if (L==-1) t[v].l=nxt++;
        add(t[v].l,l,m,x);
    } else {
        if (R==-1) t[v].r=nxt++;
        add(t[v].r,m,r,x);
    }
}
void add(ll x) {
    add(0,0,sz,x);
}
void del(int v, ll l, ll r, ll x) {
    t[v].c--, t[v].s-=x;
    if (r-l==1) return;
    ll m=(l+r)>>1;
    int L=t[v].l, R=t[v].r;
    if (x<m) {
        del(t[v].l,l,m,x);
    } else {
        del(t[v].r,m,r,x);
    }
}
void del(ll x) {
    del(0,0,sz,x);
}

ll query(int v, ll l, ll r, int k) {
    ll c=t[v].c, s=t[v].s;
    if (c==k) return s;
    if (r-l==1) return 1ll*k*l;
    ll ret=0;
    ll m=(l+r)>>1;
    int L=t[v].l, R=t[v].r;
    if (R!=-1) {
        if (t[R].c < k) {
            k-=t[R].c;
            ret+=t[R].s;
        } else return query(R,m,r,k);
    }
    return ret+query(L,l,m,k);
}
ll query(int k) {
    return query(0,0,sz,k);
}

int n,k;
ll Z[N];
void dfs3(int u, int p) {
    ans[u]=query(k);
    for(auto&e:adj[u]) {
        int v=e.f, w=e.s;
        if (v==p) continue;
        del(Z[out[v].s]);
        Z[out[v].s]+=w;
        add(Z[out[v].s]);
        del(Z[mx[v].s]);
        Z[mx[v].s]-=w;
        add(Z[mx[v].s]);
        dfs3(v,u);
        del(Z[out[v].s]);
        Z[out[v].s]-=w;
        add(Z[out[v].s]);
        del(Z[mx[v].s]);
        Z[mx[v].s]+=w;
        add(Z[mx[v].s]);
    }
}

void solve() {

	cin>>n>>k;
    forn(i,n-1) {
        int u,v,w; cin>>u>>v>>w; --u, --v;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    dfs(0,-1);
    z[zzz++]=mx[0];


    pi puiu1={0,0}, puiu2={-1,-1};
    pi x = (adj[0].size()==1)?puiu1:puiu2;
    dfs2(0,-1,x);

    if (zzz<=k) {
        ll s=0;
        forn(i,zzz) s+=z[i].f;
        forn(i,n) cout<<s<<'\n';
        return;
    }
    forn(i,zzz) {
        auto&x=z[i];
        Z[x.s]=x.f;
        add(x.f);
    }
    dfs3(0,-1);
    forn(i,n) cout<<ans[i]<<'\n';

}
     
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void del(int, ll, ll, ll)':
Main.cpp:108:9: warning: unused variable 'L' [-Wunused-variable]
  108 |     int L=t[v].l, R=t[v].r;
      |         ^
Main.cpp:108:19: warning: unused variable 'R' [-Wunused-variable]
  108 |     int L=t[v].l, R=t[v].r;
      |                   ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 228176 KB Output is correct
2 Correct 100 ms 228092 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 228176 KB Output is correct
2 Correct 100 ms 228092 KB Output is correct
3 Correct 96 ms 228044 KB Output is correct
4 Correct 102 ms 228064 KB Output is correct
5 Correct 99 ms 228056 KB Output is correct
6 Correct 105 ms 228112 KB Output is correct
7 Correct 97 ms 228168 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 228176 KB Output is correct
2 Correct 100 ms 228092 KB Output is correct
3 Correct 96 ms 228044 KB Output is correct
4 Correct 102 ms 228064 KB Output is correct
5 Correct 99 ms 228056 KB Output is correct
6 Correct 105 ms 228112 KB Output is correct
7 Correct 97 ms 228168 KB Output is correct
8 Correct 99 ms 228208 KB Output is correct
9 Correct 100 ms 228328 KB Output is correct
10 Correct 110 ms 228256 KB Output is correct
11 Correct 113 ms 228244 KB Output is correct
12 Correct 105 ms 228216 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 228176 KB Output is correct
2 Correct 100 ms 228092 KB Output is correct
3 Correct 96 ms 228044 KB Output is correct
4 Correct 102 ms 228064 KB Output is correct
5 Correct 99 ms 228056 KB Output is correct
6 Correct 105 ms 228112 KB Output is correct
7 Correct 97 ms 228168 KB Output is correct
8 Correct 99 ms 228208 KB Output is correct
9 Correct 100 ms 228328 KB Output is correct
10 Correct 110 ms 228256 KB Output is correct
11 Correct 113 ms 228244 KB Output is correct
12 Correct 105 ms 228216 KB Output is correct
13 Correct 101 ms 228300 KB Output is correct
14 Correct 101 ms 228556 KB Output is correct
15 Correct 106 ms 228492 KB Output is correct
16 Correct 113 ms 228380 KB Output is correct
17 Correct 106 ms 228384 KB Output is correct
18 Correct 100 ms 228380 KB Output is correct
19 Correct 106 ms 228300 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 240608 KB Output is correct
2 Correct 470 ms 245260 KB Output is correct
3 Correct 437 ms 239608 KB Output is correct
4 Correct 455 ms 240348 KB Output is correct
5 Correct 447 ms 242328 KB Output is correct
6 Correct 455 ms 240136 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 228176 KB Output is correct
2 Correct 100 ms 228092 KB Output is correct
3 Correct 96 ms 228044 KB Output is correct
4 Correct 102 ms 228064 KB Output is correct
5 Correct 99 ms 228056 KB Output is correct
6 Correct 105 ms 228112 KB Output is correct
7 Correct 97 ms 228168 KB Output is correct
8 Correct 99 ms 228208 KB Output is correct
9 Correct 100 ms 228328 KB Output is correct
10 Correct 110 ms 228256 KB Output is correct
11 Correct 113 ms 228244 KB Output is correct
12 Correct 105 ms 228216 KB Output is correct
13 Correct 101 ms 228300 KB Output is correct
14 Correct 101 ms 228556 KB Output is correct
15 Correct 106 ms 228492 KB Output is correct
16 Correct 113 ms 228380 KB Output is correct
17 Correct 106 ms 228384 KB Output is correct
18 Correct 100 ms 228380 KB Output is correct
19 Correct 106 ms 228300 KB Output is correct
20 Correct 461 ms 240608 KB Output is correct
21 Correct 470 ms 245260 KB Output is correct
22 Correct 437 ms 239608 KB Output is correct
23 Correct 455 ms 240348 KB Output is correct
24 Correct 447 ms 242328 KB Output is correct
25 Correct 455 ms 240136 KB Output is correct
26 Correct 490 ms 240680 KB Output is correct
27 Correct 451 ms 245144 KB Output is correct
28 Correct 464 ms 246168 KB Output is correct
29 Correct 439 ms 239708 KB Output is correct
30 Correct 466 ms 240832 KB Output is correct
31 Correct 393 ms 240200 KB Output is correct
32 Correct 466 ms 242948 KB Output is correct
33 Correct 498 ms 240680 KB Output is correct
34 Correct 445 ms 239804 KB Output is correct
35 Correct 478 ms 240804 KB Output is correct
36 Correct 481 ms 246748 KB Output is correct