oj.uz

Submission #467647

# Submission time Handle Problem Language Result Execution time Memory
467647 2021-08-23T23:54:09 Z ivan_tudor Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 5000 ms 111304 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];
multiset<long long> 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);
    }
  }
  bsum.insert(0);
  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 o_sum = sumbig2(best[centro]);
    bsum.erase(bsum.find(o_sum));

    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]);
    bsum.insert(nsum);
  }

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

    last = (*bsum.rbegin());
    cout<<last<<"\n";
  }
  return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 5 ms 7524 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 7 ms 7500 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7500 KB Output is correct
13 Correct 5 ms 7500 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7504 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 5 ms 7544 KB Output is correct
18 Correct 5 ms 7588 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 5 ms 7524 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 7 ms 7500 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7500 KB Output is correct
13 Correct 5 ms 7500 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7504 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 5 ms 7544 KB Output is correct
18 Correct 5 ms 7588 KB Output is correct
19 Correct 45 ms 8132 KB Output is correct
20 Correct 51 ms 8144 KB Output is correct
21 Correct 63 ms 8172 KB Output is correct
22 Correct 75 ms 8516 KB Output is correct
23 Correct 107 ms 11084 KB Output is correct
24 Correct 151 ms 11376 KB Output is correct
25 Correct 175 ms 11616 KB Output is correct
26 Correct 205 ms 11844 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7412 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 6 ms 7372 KB Output is correct
4 Correct 22 ms 7476 KB Output is correct
5 Correct 83 ms 7752 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 7 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 8 ms 7500 KB Output is correct
10 Correct 31 ms 7628 KB Output is correct
11 Correct 134 ms 7972 KB Output is correct
12 Correct 15 ms 8580 KB Output is correct
13 Correct 15 ms 8552 KB Output is correct
14 Correct 18 ms 8628 KB Output is correct
15 Correct 49 ms 8696 KB Output is correct
16 Correct 186 ms 9168 KB Output is correct
17 Correct 307 ms 29556 KB Output is correct
18 Correct 306 ms 29540 KB Output is correct
19 Correct 320 ms 29632 KB Output is correct
20 Correct 367 ms 29740 KB Output is correct
21 Correct 751 ms 30252 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8116 KB Output is correct
2 Correct 83 ms 8240 KB Output is correct
3 Correct 345 ms 8364 KB Output is correct
4 Correct 677 ms 8600 KB Output is correct
5 Correct 201 ms 14940 KB Output is correct
6 Correct 320 ms 15072 KB Output is correct
7 Correct 878 ms 15300 KB Output is correct
8 Correct 1479 ms 15652 KB Output is correct
9 Correct 1438 ms 58608 KB Output is correct
10 Correct 1667 ms 58596 KB Output is correct
11 Correct 2507 ms 58956 KB Output is correct
12 Correct 3653 ms 59140 KB Output is correct
13 Correct 3325 ms 111024 KB Output is correct
14 Correct 3551 ms 111008 KB Output is correct
15 Correct 4677 ms 111192 KB Output is correct
16 Execution timed out 5102 ms 111304 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5092 ms 10816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 5 ms 7524 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 7 ms 7500 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7500 KB Output is correct
13 Correct 5 ms 7500 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7504 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 5 ms 7544 KB Output is correct
18 Correct 5 ms 7588 KB Output is correct
19 Correct 45 ms 8132 KB Output is correct
20 Correct 51 ms 8144 KB Output is correct
21 Correct 63 ms 8172 KB Output is correct
22 Correct 75 ms 8516 KB Output is correct
23 Correct 107 ms 11084 KB Output is correct
24 Correct 151 ms 11376 KB Output is correct
25 Correct 175 ms 11616 KB Output is correct
26 Correct 205 ms 11844 KB Output is correct
27 Correct 4 ms 7412 KB Output is correct
28 Correct 5 ms 7372 KB Output is correct
29 Correct 6 ms 7372 KB Output is correct
30 Correct 22 ms 7476 KB Output is correct
31 Correct 83 ms 7752 KB Output is correct
32 Correct 4 ms 7372 KB Output is correct
33 Correct 7 ms 7500 KB Output is correct
34 Correct 5 ms 7500 KB Output is correct
35 Correct 8 ms 7500 KB Output is correct
36 Correct 31 ms 7628 KB Output is correct
37 Correct 134 ms 7972 KB Output is correct
38 Correct 15 ms 8580 KB Output is correct
39 Correct 15 ms 8552 KB Output is correct
40 Correct 18 ms 8628 KB Output is correct
41 Correct 49 ms 8696 KB Output is correct
42 Correct 186 ms 9168 KB Output is correct
43 Correct 307 ms 29556 KB Output is correct
44 Correct 306 ms 29540 KB Output is correct
45 Correct 320 ms 29632 KB Output is correct
46 Correct 367 ms 29740 KB Output is correct
47 Correct 751 ms 30252 KB Output is correct
48 Correct 22 ms 8116 KB Output is correct
49 Correct 83 ms 8240 KB Output is correct
50 Correct 345 ms 8364 KB Output is correct
51 Correct 677 ms 8600 KB Output is correct
52 Correct 201 ms 14940 KB Output is correct
53 Correct 320 ms 15072 KB Output is correct
54 Correct 878 ms 15300 KB Output is correct
55 Correct 1479 ms 15652 KB Output is correct
56 Correct 1438 ms 58608 KB Output is correct
57 Correct 1667 ms 58596 KB Output is correct
58 Correct 2507 ms 58956 KB Output is correct
59 Correct 3653 ms 59140 KB Output is correct
60 Correct 3325 ms 111024 KB Output is correct
61 Correct 3551 ms 111008 KB Output is correct
62 Correct 4677 ms 111192 KB Output is correct
63 Execution timed out 5102 ms 111304 KB Time limit exceeded
64 Halted 0 ms 0 KB -