oj.uz

답안 #467655

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467655 2021-08-24T00:14:00 Z ivan_tudor Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 5000 ms 140092 KB 
#include<bits/stdc++.h>
using namespace std;
// consideram initial ca toate distantele sunt 0 si apoi updatam cu costul muchiilor
const int N = 100005;
const int LOGN = 18;

// aint
long long aint[N * LOGN * 4 + 5];
long long lazy[N * LOGN * 4 + 5];
void propag(int nod, int l, int r){
  aint[nod] += 1LL * lazy[nod];
  if(l != r){
    lazy[2*nod] += lazy[nod];
    lazy[2*nod + 1] += lazy[nod];
  }
  lazy[nod] = 0;
}
void update(int nod, int l, int r, int ul, int ur, long long val){
  propag(nod, l, r);
  if(ur < l || r < ul)
    return;
  if(ul <= l && r <= ur){
    lazy[nod] += val;
    propag(nod, l, r);
    return;
  }
  int mid = (l + r)/2;
  update(2*nod, l, mid, ul, ur, val);
  update(2*nod + 1, mid + 1, r, ul, ur, val);
  aint[nod] = max(aint[2*nod], aint[2*nod + 1]);
}
long long query(int nod, int l, int r, int ql, int qr){
  propag(nod, l, r);
  if(r < ql || qr < l)
    return 0;
  if(ql <= l && r <= qr)
    return aint[nod];
  int mid = (l + r)/2;
  long long ls = query(2*nod, l, mid, ql, qr);
  long long rs = query(2*nod + 1, mid + 1, r, ql, qr);
  return max(ls, rs);
}
vector<int> gr[N];
int croot[LOGN][N];
int fson[LOGN][N];
int in[LOGN][N];
int out[LOGN][N];

bool wasC[N];
int sz[N];
void dfs_sz(int nod, int dad){
  sz[nod] = 1;
  for(auto x:gr[nod]){
    if(x!= dad && wasC[x] == false){
      dfs_sz(x, nod);
      sz[nod] += sz[x];
    }
  }
}
int find_centro(int nod, int dad, int bound){
  for(auto x:gr[nod]){
    if(wasC[x] == false && x!= dad && sz[x] > bound)
      return find_centro(x, nod, bound);
  }
  return nod;
}
void dfs_from_centro(int nod, int dad, int cnumber, int &id, int centro, int fs){
  if(dad == centro)
    fs = nod;
  croot[cnumber][nod] = centro;
  fson[cnumber][nod] = fs;
  in[cnumber][nod] = ++id;
  for(auto x:gr[nod]){
    if(x != dad && wasC[x] == false){
      dfs_from_centro(x, nod, cnumber, id, centro, fs);
    }
  }
  out[cnumber][nod] = id;
}
multiset<long long> best[N];

long long bs[N];
priority_queue<pair<long long, int>> bsum;
void centro_dec(int nod, int number, int &id){
  dfs_sz(nod, 0);
  int sze = sz[nod];
  int centro = find_centro(nod, 0, sze / 2);
  dfs_from_centro(centro, 0, number, id, centro, centro);
  for(auto x:gr[centro]){
    if(wasC[x] == false){
      best[centro].insert(0);
    }
  }
  bs[nod] = 0;
  bsum.push({bs[nod], nod});
  wasC[centro] = true;
  for(auto x:gr[centro]){
    if(wasC[x] == false)
      centro_dec(x, number + 1, id);
  }

}
int L, R;
long long sumbig2(multiset<long long> &s){
  long long sum =0;
  int cnt = 0;
  for(auto itr = s.rbegin(); itr != s.rend() && cnt < 2; itr++, cnt++){
    sum += (*itr);
  }
  return sum;
}
bool isdad(int number, int dad, int son){
  if(in[number][dad] <= in[number][son] && out[number][son] <= out[number][dad])
    return true;
  return false;
}
void update_edge(int nod, int onod, long long change){
  int number = 0;
  for(; number < LOGN; number++){
    if(croot[number][nod] == nod)
      break;
  }
  while(number > 0 && croot[number][nod] != croot[number][onod])
    number--;
  for(; number >= 0; number--){
    if(isdad(number, nod, onod) == true)
      swap(nod, onod);

    int centro = croot[number][nod];
    int fs = fson[number][nod];

    long long old_big = query(1, L, R, in[number][fs], out[number][fs]);
    best[centro].erase(best[centro].find(old_big));

    update(1, L, R, in[number][nod], out[number][nod], change);

    long long new_big = query(1, L, R, in[number][fs], out[number][fs]);
    best[centro].insert(new_big);

    long long nsum = sumbig2(best[centro]);
    bs[centro] = nsum;
    bsum.push({nsum, centro});
  }

}
struct edges{
  int x, y;
  long long c;
};
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, q;
  long long w;
  cin>>n>>q>>w;
  vector<edges> es;
  for(int i = 0; i < n - 1; i++){
    int x, y, c;
    cin>>x>>y>>c;
    es.push_back({x, y, c});
    gr[x].push_back(y);
    gr[y].push_back(x);
  }
  centro_dec(1, 0, R);
  L = 1;
  for(int i = 0; i < n - 1; i++){
    update_edge(es[i].x, es[i].y, es[i].c);
  }
  long long last = 0;
  for(int i = 1; i<=q; i++){

    long long d, e;
    cin>>d>>e;
    d = (last + d)%(n - 1);
    e = (last + e)% w;

    long long df = e - es[d].c;
    update_edge(es[d].x, es[d].y, df);
    es[d].c = e;

    while(bsum.size() && bs[bsum.top().second] != bsum.top().first)
      bsum.pop();
    last = bsum.top().first;
    cout<<last<<"\n";
  }
  return 0;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7484 KB Output is correct
4 Correct 5 ms 7384 KB Output is correct
5 Correct 4 ms 7460 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 4 ms 7500 KB Output is correct
8 Correct 4 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 5 ms 7500 KB Output is correct
11 Correct 5 ms 7516 KB Output is correct
12 Correct 6 ms 7500 KB Output is correct
13 Correct 6 ms 7564 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7500 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 6 ms 7500 KB Output is correct
18 Correct 5 ms 7500 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7484 KB Output is correct
4 Correct 5 ms 7384 KB Output is correct
5 Correct 4 ms 7460 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 4 ms 7500 KB Output is correct
8 Correct 4 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 5 ms 7500 KB Output is correct
11 Correct 5 ms 7516 KB Output is correct
12 Correct 6 ms 7500 KB Output is correct
13 Correct 6 ms 7564 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7500 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 6 ms 7500 KB Output is correct
18 Correct 5 ms 7500 KB Output is correct
19 Correct 43 ms 8416 KB Output is correct
20 Correct 49 ms 8388 KB Output is correct
21 Correct 59 ms 8760 KB Output is correct
22 Correct 74 ms 9500 KB Output is correct
23 Correct 102 ms 11964 KB Output is correct
24 Correct 150 ms 12184 KB Output is correct
25 Correct 185 ms 12328 KB Output is correct
26 Correct 196 ms 13824 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 9 ms 7372 KB Output is correct
4 Correct 20 ms 7492 KB Output is correct
5 Correct 83 ms 7772 KB Output is correct
6 Correct 5 ms 7320 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 5 ms 7568 KB Output is correct
9 Correct 8 ms 7576 KB Output is correct
10 Correct 30 ms 7628 KB Output is correct
11 Correct 128 ms 8004 KB Output is correct
12 Correct 14 ms 8764 KB Output is correct
13 Correct 16 ms 8652 KB Output is correct
14 Correct 17 ms 8684 KB Output is correct
15 Correct 46 ms 8788 KB Output is correct
16 Correct 177 ms 9192 KB Output is correct
17 Correct 254 ms 29120 KB Output is correct
18 Correct 264 ms 28968 KB Output is correct
19 Correct 255 ms 28968 KB Output is correct
20 Correct 323 ms 29068 KB Output is correct
21 Correct 632 ms 29704 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 8388 KB Output is correct
2 Correct 85 ms 8652 KB Output is correct
3 Correct 351 ms 10392 KB Output is correct
4 Correct 659 ms 12592 KB Output is correct
5 Correct 187 ms 16692 KB Output is correct
6 Correct 295 ms 16740 KB Output is correct
7 Correct 868 ms 18876 KB Output is correct
8 Correct 1449 ms 23360 KB Output is correct
9 Correct 1229 ms 73112 KB Output is correct
10 Correct 1460 ms 73080 KB Output is correct
11 Correct 2189 ms 73188 KB Output is correct
12 Correct 3150 ms 73132 KB Output is correct
13 Correct 2723 ms 139808 KB Output is correct
14 Correct 3020 ms 139896 KB Output is correct
15 Correct 3919 ms 140092 KB Output is correct
16 Execution timed out 5064 ms 139824 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5056 ms 10816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7484 KB Output is correct
4 Correct 5 ms 7384 KB Output is correct
5 Correct 4 ms 7460 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 4 ms 7500 KB Output is correct
8 Correct 4 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 5 ms 7500 KB Output is correct
11 Correct 5 ms 7516 KB Output is correct
12 Correct 6 ms 7500 KB Output is correct
13 Correct 6 ms 7564 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7500 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 6 ms 7500 KB Output is correct
18 Correct 5 ms 7500 KB Output is correct
19 Correct 43 ms 8416 KB Output is correct
20 Correct 49 ms 8388 KB Output is correct
21 Correct 59 ms 8760 KB Output is correct
22 Correct 74 ms 9500 KB Output is correct
23 Correct 102 ms 11964 KB Output is correct
24 Correct 150 ms 12184 KB Output is correct
25 Correct 185 ms 12328 KB Output is correct
26 Correct 196 ms 13824 KB Output is correct
27 Correct 4 ms 7372 KB Output is correct
28 Correct 5 ms 7372 KB Output is correct
29 Correct 9 ms 7372 KB Output is correct
30 Correct 20 ms 7492 KB Output is correct
31 Correct 83 ms 7772 KB Output is correct
32 Correct 5 ms 7320 KB Output is correct
33 Correct 5 ms 7500 KB Output is correct
34 Correct 5 ms 7568 KB Output is correct
35 Correct 8 ms 7576 KB Output is correct
36 Correct 30 ms 7628 KB Output is correct
37 Correct 128 ms 8004 KB Output is correct
38 Correct 14 ms 8764 KB Output is correct
39 Correct 16 ms 8652 KB Output is correct
40 Correct 17 ms 8684 KB Output is correct
41 Correct 46 ms 8788 KB Output is correct
42 Correct 177 ms 9192 KB Output is correct
43 Correct 254 ms 29120 KB Output is correct
44 Correct 264 ms 28968 KB Output is correct
45 Correct 255 ms 28968 KB Output is correct
46 Correct 323 ms 29068 KB Output is correct
47 Correct 632 ms 29704 KB Output is correct
48 Correct 24 ms 8388 KB Output is correct
49 Correct 85 ms 8652 KB Output is correct
50 Correct 351 ms 10392 KB Output is correct
51 Correct 659 ms 12592 KB Output is correct
52 Correct 187 ms 16692 KB Output is correct
53 Correct 295 ms 16740 KB Output is correct
54 Correct 868 ms 18876 KB Output is correct
55 Correct 1449 ms 23360 KB Output is correct
56 Correct 1229 ms 73112 KB Output is correct
57 Correct 1460 ms 73080 KB Output is correct
58 Correct 2189 ms 73188 KB Output is correct
59 Correct 3150 ms 73132 KB Output is correct
60 Correct 2723 ms 139808 KB Output is correct
61 Correct 3020 ms 139896 KB Output is correct
62 Correct 3919 ms 140092 KB Output is correct
63 Execution timed out 5064 ms 139824 KB Time limit exceeded
64 Halted 0 ms 0 KB -