oj.uz

Submission #467640

# Submission time Handle Problem Language Result Execution time Memory
467640 2021-08-23T23:32:54 Z ivan_tudor Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 5000 ms 113956 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 4 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 7496 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 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 7500 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 5 ms 7500 KB Output is correct
18 Correct 5 ms 7500 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 4 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 7496 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 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 7500 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 5 ms 7500 KB Output is correct
18 Correct 5 ms 7500 KB Output is correct
19 Correct 47 ms 8132 KB Output is correct
20 Correct 50 ms 8140 KB Output is correct
21 Correct 60 ms 8176 KB Output is correct
22 Correct 79 ms 8584 KB Output is correct
23 Correct 113 ms 11068 KB Output is correct
24 Correct 150 ms 11352 KB Output is correct
25 Correct 171 ms 11476 KB Output is correct
26 Correct 214 ms 11856 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7344 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 6 ms 7372 KB Output is correct
4 Correct 20 ms 7500 KB Output is correct
5 Correct 85 ms 7744 KB Output is correct
6 Correct 4 ms 7360 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 6 ms 7500 KB Output is correct
9 Correct 8 ms 7444 KB Output is correct
10 Correct 36 ms 7628 KB Output is correct
11 Correct 129 ms 7980 KB Output is correct
12 Correct 15 ms 8640 KB Output is correct
13 Correct 15 ms 8636 KB Output is correct
14 Correct 20 ms 8584 KB Output is correct
15 Correct 49 ms 8652 KB Output is correct
16 Correct 190 ms 9028 KB Output is correct
17 Correct 299 ms 29580 KB Output is correct
18 Correct 311 ms 29744 KB Output is correct
19 Correct 303 ms 29624 KB Output is correct
20 Correct 369 ms 29816 KB Output is correct
21 Correct 679 ms 30304 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8100 KB Output is correct
2 Correct 81 ms 8124 KB Output is correct
3 Correct 350 ms 8384 KB Output is correct
4 Correct 689 ms 9396 KB Output is correct
5 Correct 208 ms 15268 KB Output is correct
6 Correct 325 ms 15240 KB Output is correct
7 Correct 831 ms 15968 KB Output is correct
8 Correct 1569 ms 16704 KB Output is correct
9 Correct 1392 ms 59392 KB Output is correct
10 Correct 1607 ms 59640 KB Output is correct
11 Correct 2446 ms 60392 KB Output is correct
12 Correct 3521 ms 61020 KB Output is correct
13 Correct 3354 ms 112572 KB Output is correct
14 Correct 3514 ms 112628 KB Output is correct
15 Correct 4604 ms 113360 KB Output is correct
16 Execution timed out 5048 ms 113956 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 5029 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 4 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 7496 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 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 7500 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 5 ms 7500 KB Output is correct
18 Correct 5 ms 7500 KB Output is correct
19 Correct 47 ms 8132 KB Output is correct
20 Correct 50 ms 8140 KB Output is correct
21 Correct 60 ms 8176 KB Output is correct
22 Correct 79 ms 8584 KB Output is correct
23 Correct 113 ms 11068 KB Output is correct
24 Correct 150 ms 11352 KB Output is correct
25 Correct 171 ms 11476 KB Output is correct
26 Correct 214 ms 11856 KB Output is correct
27 Correct 4 ms 7344 KB Output is correct
28 Correct 4 ms 7372 KB Output is correct
29 Correct 6 ms 7372 KB Output is correct
30 Correct 20 ms 7500 KB Output is correct
31 Correct 85 ms 7744 KB Output is correct
32 Correct 4 ms 7360 KB Output is correct
33 Correct 5 ms 7500 KB Output is correct
34 Correct 6 ms 7500 KB Output is correct
35 Correct 8 ms 7444 KB Output is correct
36 Correct 36 ms 7628 KB Output is correct
37 Correct 129 ms 7980 KB Output is correct
38 Correct 15 ms 8640 KB Output is correct
39 Correct 15 ms 8636 KB Output is correct
40 Correct 20 ms 8584 KB Output is correct
41 Correct 49 ms 8652 KB Output is correct
42 Correct 190 ms 9028 KB Output is correct
43 Correct 299 ms 29580 KB Output is correct
44 Correct 311 ms 29744 KB Output is correct
45 Correct 303 ms 29624 KB Output is correct
46 Correct 369 ms 29816 KB Output is correct
47 Correct 679 ms 30304 KB Output is correct
48 Correct 21 ms 8100 KB Output is correct
49 Correct 81 ms 8124 KB Output is correct
50 Correct 350 ms 8384 KB Output is correct
51 Correct 689 ms 9396 KB Output is correct
52 Correct 208 ms 15268 KB Output is correct
53 Correct 325 ms 15240 KB Output is correct
54 Correct 831 ms 15968 KB Output is correct
55 Correct 1569 ms 16704 KB Output is correct
56 Correct 1392 ms 59392 KB Output is correct
57 Correct 1607 ms 59640 KB Output is correct
58 Correct 2446 ms 60392 KB Output is correct
59 Correct 3521 ms 61020 KB Output is correct
60 Correct 3354 ms 112572 KB Output is correct
61 Correct 3514 ms 112628 KB Output is correct
62 Correct 4604 ms 113360 KB Output is correct
63 Execution timed out 5048 ms 113956 KB Time limit exceeded
64 Halted 0 ms 0 KB -