oj.uz

Submission #1019971

# Submission time Handle Problem Language Result Execution time Memory
1019971 2024-07-11T11:34:56 Z NintsiChkhaidze Paths (RMI21_paths) C++17
48 / 100
 600 ms 26620 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 (i != d1 && i != d2)
      getans(i);
  }

  printans();
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14424 KB Output is correct
2 Correct 2 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 6 ms 14672 KB Output is correct
5 Correct 4 ms 14428 KB Output is correct
6 Correct 9 ms 14512 KB Output is correct
7 Correct 6 ms 14428 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14424 KB Output is correct
2 Correct 2 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 6 ms 14672 KB Output is correct
5 Correct 4 ms 14428 KB Output is correct
6 Correct 9 ms 14512 KB Output is correct
7 Correct 6 ms 14428 KB Output is correct
8 Correct 91 ms 14760 KB Output is correct
9 Correct 146 ms 14680 KB Output is correct
10 Correct 155 ms 14684 KB Output is correct
11 Correct 48 ms 14680 KB Output is correct
12 Correct 95 ms 14680 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14424 KB Output is correct
2 Correct 2 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 6 ms 14672 KB Output is correct
5 Correct 4 ms 14428 KB Output is correct
6 Correct 9 ms 14512 KB Output is correct
7 Correct 6 ms 14428 KB Output is correct
8 Correct 91 ms 14760 KB Output is correct
9 Correct 146 ms 14680 KB Output is correct
10 Correct 155 ms 14684 KB Output is correct
11 Correct 48 ms 14680 KB Output is correct
12 Correct 95 ms 14680 KB Output is correct
13 Execution timed out 661 ms 14680 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 24712 KB Output is correct
2 Correct 245 ms 26620 KB Output is correct
3 Correct 235 ms 24576 KB Output is correct
4 Correct 245 ms 24572 KB Output is correct
5 Correct 312 ms 25408 KB Output is correct
6 Correct 233 ms 25120 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14424 KB Output is correct
2 Correct 2 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 6 ms 14672 KB Output is correct
5 Correct 4 ms 14428 KB Output is correct
6 Correct 9 ms 14512 KB Output is correct
7 Correct 6 ms 14428 KB Output is correct
8 Correct 91 ms 14760 KB Output is correct
9 Correct 146 ms 14680 KB Output is correct
10 Correct 155 ms 14684 KB Output is correct
11 Correct 48 ms 14680 KB Output is correct
12 Correct 95 ms 14680 KB Output is correct
13 Execution timed out 661 ms 14680 KB Time limit exceeded
14 Halted 0 ms 0 KB -