oj.uz

답안 #1019913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1019913 2024-07-11T10:38:48 Z NintsiChkhaidze Paths (RMI21_paths) C++17
48 / 100
 600 ms 31672 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 = 2e5 + 5;
vector <pii> v[N];
int I,D,timer,tin[N],tout[N],ans[N],dp[N];
int d1,d2;
pii t[4*N];
bool fix[N];
int pr[N];
int lz[4*N],n,k,rev[N],edge[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;

  ans[x] = 0;
  for (int i = 1; i <= k; i++){
    int y = t[1].s;
    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);
  }
}

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

  cin>>n>>k;

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

  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);
    for (int i = 1; i <= n; i++){
      cout<<ans[i]<<endl;
    }
    exit(0);
  }

  for (int i = 1; i <= n; i++){
    getans(i);
    cout<<ans[i]<<endl;
  }
  // getans(d1);
  // getans(d2);

}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18264 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18264 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 6 ms 18524 KB Output is correct
4 Correct 8 ms 18524 KB Output is correct
5 Correct 4 ms 18524 KB Output is correct
6 Correct 8 ms 18520 KB Output is correct
7 Correct 7 ms 18480 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18264 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 6 ms 18524 KB Output is correct
4 Correct 8 ms 18524 KB Output is correct
5 Correct 4 ms 18524 KB Output is correct
6 Correct 8 ms 18520 KB Output is correct
7 Correct 7 ms 18480 KB Output is correct
8 Correct 94 ms 18524 KB Output is correct
9 Correct 172 ms 18624 KB Output is correct
10 Correct 156 ms 18616 KB Output is correct
11 Correct 49 ms 18524 KB Output is correct
12 Correct 96 ms 18588 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18264 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 6 ms 18524 KB Output is correct
4 Correct 8 ms 18524 KB Output is correct
5 Correct 4 ms 18524 KB Output is correct
6 Correct 8 ms 18520 KB Output is correct
7 Correct 7 ms 18480 KB Output is correct
8 Correct 94 ms 18524 KB Output is correct
9 Correct 172 ms 18624 KB Output is correct
10 Correct 156 ms 18616 KB Output is correct
11 Correct 49 ms 18524 KB Output is correct
12 Correct 96 ms 18588 KB Output is correct
13 Execution timed out 694 ms 18664 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 268 ms 29780 KB Output is correct
2 Correct 275 ms 31672 KB Output is correct
3 Correct 250 ms 29264 KB Output is correct
4 Correct 244 ms 29452 KB Output is correct
5 Correct 269 ms 30292 KB Output is correct
6 Correct 252 ms 29364 KB Output is correct

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18264 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 6 ms 18524 KB Output is correct
4 Correct 8 ms 18524 KB Output is correct
5 Correct 4 ms 18524 KB Output is correct
6 Correct 8 ms 18520 KB Output is correct
7 Correct 7 ms 18480 KB Output is correct
8 Correct 94 ms 18524 KB Output is correct
9 Correct 172 ms 18624 KB Output is correct
10 Correct 156 ms 18616 KB Output is correct
11 Correct 49 ms 18524 KB Output is correct
12 Correct 96 ms 18588 KB Output is correct
13 Execution timed out 694 ms 18664 KB Time limit exceeded
14 Halted 0 ms 0 KB -