Submission #467632

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
467632	2021-08-23T22:29:41 Z	ivan_tudor	Dynamic Diameter (CEOI19_diameter)	C++14	7 / 100	5000 ms	32744 KB

diameter

#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;
  }
  if(isdad(number, nod, onod) == false)
    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);
  }
  cerr<<(*bsum.rbegin())<<"\n      ==================== \n";
  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
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	7372 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	7372 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.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	6 ms	7372 KB	Output is correct
4	Correct	21 ms	7616 KB	Output is correct
5	Correct	95 ms	8516 KB	Output is correct
6	Correct	5 ms	7368 KB	Output is correct
7	Correct	6 ms	7528 KB	Output is correct
8	Correct	6 ms	7500 KB	Output is correct
9	Correct	8 ms	7500 KB	Output is correct
10	Correct	31 ms	7816 KB	Output is correct
11	Correct	137 ms	8780 KB	Output is correct
12	Correct	15 ms	8652 KB	Output is correct
13	Correct	16 ms	8628 KB	Output is correct
14	Correct	19 ms	8648 KB	Output is correct
15	Correct	52 ms	8976 KB	Output is correct
16	Correct	195 ms	10048 KB	Output is correct
17	Correct	336 ms	30796 KB	Output is correct
18	Correct	321 ms	30792 KB	Output is correct
19	Correct	311 ms	30884 KB	Output is correct
20	Correct	384 ms	31228 KB	Output is correct
21	Correct	672 ms	32744 KB	Output is correct