oj.uz

Submission #1019970

# Submission time Handle Problem Language Result Execution time Memory
1019970 2024-07-11T11:33:51 Z NintsiChkhaidze Paths (RMI21_paths) C++17
12 / 100
 291 ms 29112 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,d2,A,val[N],tot;
bool fix[N],mark[N],spc[N];
int pr[N],arr[N],dep[N],dd[25][N];
int lz[4*N],n,k,rev[N],edge[N];
pii t[4*N],DD[N];

void godfs(int x,int par){
  for (auto [to,w]: v[x]){
    if (to == par) continue;
    godfs(to,x);
    val[x] += val[to];
  }
  if (val[x] > 0) mark[x] = 1;
}

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){
  dd[0][x] = par;
  dep[x] = dep[par] + 1;
  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;

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

}

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

int lca(int x,int y){
  if (dep[x] < dep[y]) swap(x,y);
  for (int j=20;j>=0;j--)
    if (dep[dd[j][x]] >= dep[y]) x=dd[j][x];
  if(x==y) return x;
  for (int j=20;j>=0;j--)
    if (dd[j][x] != dd[j][y]) x=dd[j][x],y=dd[j][y];
  return dd[0][x];
}

void ddfs(int x,int par,int distance){
  if (!spc[x]) ans[x] = distance + tot;
  for (auto [to,w]: v[x]){
    if (to != par && !mark[to]) {
      ddfs(to,x,distance + w);
    }
  }
}

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;
  I = D = 0;
  dfs(d1,d1,0);
  d2 = I;

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

  getans(d1);
  getans(d2);
  if (n == 2) printans();

  for (int i = 1; i <= 3; i++){
    if (i != d1 && i != d2){
      A=i; break;
    }
  }

  getans(A);
  timer = 0; go(1,1,0);
  for(int j=1;j<=20;j++)
    for (int i=1;i<=n;i++)
      dd[j][i]=dd[j-1][dd[j - 1][i]];
    
  for (int i = 1; i <= k; i++){
    DD[i] = {tin[arr[i]],arr[i]};
    spc[arr[i]] = 1;
  }
  sort(DD+1,DD+k+1);
  for (int i = 2; i <= k; i++){
    val[DD[i].s] += 1;
    val[DD[i - 1].s] += 1;
    int c = lca(DD[i].s,DD[i-1].s);
    if (c == 1) c = 0;
    else c = dd[0][c];
    val[c] -= 2;
  }

  godfs(1,1);
  for (int i=0;i<n;i++){
    if (mark[edges[i].f.f] && mark[edges[i].f.s]){
      tot += edges[i].s;
    }
  }
  
  for (int i = 1; i <= n; i++){
    if (mark[i]) ddfs(i,i,0);    
  }

  //k * n * logn
  for (int i =1;  i<= n; i++){
    if (spc[i] && i != d1 && i != d2)
      getans(i);
  }

  printans();
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 28764 KB Output is correct
2 Incorrect 4 ms 28764 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 291 ms 26716 KB Output is correct
2 Correct 291 ms 29112 KB Output is correct
3 Correct 270 ms 26616 KB Output is correct
4 Correct 281 ms 26580 KB Output is correct
5 Correct 264 ms 27644 KB Output is correct
6 Correct 245 ms 26620 KB Output is correct

Subtask #6
0 / 32.0

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