oj.uz

Submission #1019987

# Submission time Handle Problem Language Result Execution time Memory
1019987 2024-07-11T11:50:07 Z NintsiChkhaidze Paths (RMI21_paths) C++17
12 / 100
 281 ms 25348 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define int ll
using namespace std;

const int N = 1e5 + 5,inf = 1e18;
vector <pii> v[N];
int I,D,timer,tin[N],tout[N],ans[N],dp[N];
int d1,tot;
bool fix[N],spc[N];
int pr[N],arr[N];
int lz[4*N],n,k,rev[N],edge[N];
pii t[4*N];

void predfs(int x,int par){
  tin[x] = ++timer;
  rev[timer] =x;
  for (auto [to,w]: v[x]){
    if (to == par) continue;
    dp[to] = dp[x] + w;
    predfs(to,x);
  }
  tout[x] = timer;
}

void go(int x,int par,int d){
  tin[x] = ++timer;
  rev[timer] =x;
  dp[x] = d;
  pr[x] = par;
  for (auto [to,w]: v[x]){
    if (to == par) continue;
    edge[to] = w;
    go(to,x,d+w);
  }
  tout[x] = timer;
}

void dfs(int x,int par,int d){
  if (d > D) D = d,I = x;
  for (auto [to,w]: v[x]){
    if (to == par) continue;
    dfs(to,x,d + w);
  }
}

void build(int h,int l,int r){
  lz[h] = 0;
  if (l == r){
    t[h] = {dp[rev[l]],rev[l]};
    return;
  }

  build(left); build(right);
  t[h] = max(t[h*2],t[h*2+1]);
}

void push(int h){
  if (lz[h]==0) return;
  lz[h*2] += lz[h];
  lz[h*2+1] += lz[h];
  t[h*2].f += lz[h];
  t[h*2 + 1].f += lz[h];
  lz[h] = 0;
}

void upd(int h,int l,int r,int L,int R,int val){
  if (r < L || R < l) return;
  if (L <= l && r <= R){
    t[h].f += val;
    lz[h] += val;
    return;
  }
  push(h);
  upd(left,L,R,val);
  upd(right,L,R,val);
  t[h] = max(t[h*2],t[h*2+1]);
}

void getans(int x){
  timer = 0; go(x,x,0);
  build(1,1,n);

  for (int i = 1; i <= n; i++)
    fix[i] = 1;
  fix[x] = 0; 

  spc[x] = 1;
  for (int i = 1; i < k; i++){
    int y = t[1].s;
    arr[i] = y; spc[y] = 1;
    tot += t[1].f;
    while (fix[y]){
      upd(1,1,n,tin[y],tout[y],-edge[y]);
      edge[y] = 0;
      fix[y] = 0;
      y = pr[y];
    }
  }
}

int get(int h,int l,int r,int idx){
  if (l == r) return t[h].f;
  push(h);
  if (idx > (l + r)/2) return get(right,idx);
  return get(left,idx);
}

void godfs(int x,int par){
  if (spc[x]) ans[x] = tot + t[1].f;
  else ans[x] = tot + get(1,1,n,1);

  for (auto [to,w]: v[x]){
    if (to == par) continue;
    w = edge[to];
    upd(1,1,n,tin[to],tout[to],-w);
    upd(1,1,n,1,tin[to] - 1,+w);
    upd(1,1,n,tout[to] + 1,n,+w);

    godfs(to,x);

    upd(1,1,n,tin[to],tout[to],+w);
    upd(1,1,n,1,tin[to] - 1,-w);
    upd(1,1,n,tout[to] + 1,n,-w);
  }

}

void calc(int x,int par){
  if (k == 1){
    ans[x] = t[1].f;
  }

  for (auto [to,w]: v[x]){
    if (to == par) continue;
    upd(1,1,n,tin[to],tout[to],-w);
    upd(1,1,n,1,tin[to] - 1,+w);
    upd(1,1,n,tout[to] + 1,n,+w);

    calc(to,x); 

    upd(1,1,n,tin[to],tout[to],+w);
    upd(1,1,n,1,tin[to] - 1,-w);
    upd(1,1,n,tout[to] + 1,n,-w);
  }
}

void printans(){
  for (int i= 1; i <= n; i++)
    cout<<ans[i]<<endl;
  exit(0);
}

signed main() {
  ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

  cin>>n>>k;
  vector <pair <pii,int> > edges;
  for (int i = 1; i < n; i++){
    int a,b,c;
    cin>>a>>b>>c;
    v[a].pb({b,c});
    v[b].pb({a,c});
    edges.pb({{a,b},c});
  }

  predfs(1,1);
  dfs(1,1,0);
  d1 = I;
  
  if (k == 1){
    build(1,1,n);
    calc(1,1);
    printans();
    exit(0);
  }

  getans(d1);
  godfs(d1,d1);
  printans();
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10072 KB Output is correct
2 Incorrect 2 ms 10072 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 248 ms 22784 KB Output is correct
2 Correct 244 ms 25348 KB Output is correct
3 Correct 254 ms 22780 KB Output is correct
4 Correct 256 ms 23076 KB Output is correct
5 Correct 254 ms 24196 KB Output is correct
6 Correct 281 ms 22628 KB Output is correct

Subtask #6
0 / 32.0

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