oj.uz

답안 #1019895

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1019895 2024-07-11T10:24:39 Z NintsiChkhaidze Paths (RMI21_paths) C++17
12 / 100
 248 ms 32080 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];
pii t[4*N];
int lz[4*N],n,k,rev[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 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){
  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 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);
  int d1 = I;
  I = D = 0;
  dfs(d1,d1,0);
  int 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);
  }


}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:107:7: warning: unused variable 'd2' [-Wunused-variable]
  107 |   int d2 = I;
      |       ^~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 241 ms 27988 KB Output is correct
2 Correct 240 ms 32080 KB Output is correct
3 Correct 242 ms 29872 KB Output is correct
4 Correct 234 ms 29900 KB Output is correct
5 Correct 239 ms 30820 KB Output is correct
6 Correct 248 ms 29812 KB Output is correct

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -