oj.uz

답안 #467638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467638 2021-08-23T23:31:01 Z ivan_tudor Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 5000 ms 31664 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];
    if(centro == 4){
      cerr<<"!!dbg best[4] before adding "<<change<<" to "<<nod<<" :\n";
      for(auto x:best[4])
        cerr<<x<<" ";
      cerr<<"\n\n";

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

    if(centro == 4){
      cerr<<"!!dbg best[4] after adding "<<change<<" to "<<nod<<" :\n";
      for(auto x:best[4])
        cerr<<x<<" ";
      cerr<<"\n\n";

    }

    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;

    if(d == 4){
        cerr<<"edges at the moment " <<i<<":\n";
        for(auto x:es){
          cerr<<x.x<<" "<<x.y<<" "<<x.c<<"\n";
        }
      }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 5 ms 7368 KB Output is correct
4 Correct 5 ms 7376 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 6 ms 7500 KB Output is correct
8 Correct 8 ms 7500 KB Output is correct
9 Correct 6 ms 7448 KB Output is correct
10 Correct 6 ms 7500 KB Output is correct
11 Correct 7 ms 7500 KB Output is correct
12 Correct 7 ms 7500 KB Output is correct
13 Correct 5 ms 7496 KB Output is correct
14 Correct 6 ms 7500 KB Output is correct
15 Correct 5 ms 7544 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 5 ms 7500 KB Output is correct
18 Correct 8 ms 7500 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 5 ms 7368 KB Output is correct
4 Correct 5 ms 7376 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 6 ms 7500 KB Output is correct
8 Correct 8 ms 7500 KB Output is correct
9 Correct 6 ms 7448 KB Output is correct
10 Correct 6 ms 7500 KB Output is correct
11 Correct 7 ms 7500 KB Output is correct
12 Correct 7 ms 7500 KB Output is correct
13 Correct 5 ms 7496 KB Output is correct
14 Correct 6 ms 7500 KB Output is correct
15 Correct 5 ms 7544 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 5 ms 7500 KB Output is correct
18 Correct 8 ms 7500 KB Output is correct
19 Correct 111 ms 8140 KB Output is correct
20 Correct 122 ms 8236 KB Output is correct
21 Correct 77 ms 8260 KB Output is correct
22 Correct 108 ms 8568 KB Output is correct
23 Correct 164 ms 11336 KB Output is correct
24 Correct 160 ms 11496 KB Output is correct
25 Correct 225 ms 11728 KB Output is correct
26 Correct 207 ms 11956 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 28 ms 7372 KB Output is correct
4 Correct 217 ms 7684 KB Output is correct
5 Correct 1096 ms 8716 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 6 ms 7464 KB Output is correct
8 Correct 6 ms 7500 KB Output is correct
9 Correct 13 ms 7500 KB Output is correct
10 Correct 215 ms 7776 KB Output is correct
11 Correct 1022 ms 8860 KB Output is correct
12 Correct 17 ms 8652 KB Output is correct
13 Correct 15 ms 8652 KB Output is correct
14 Correct 18 ms 8640 KB Output is correct
15 Correct 185 ms 8772 KB Output is correct
16 Correct 1319 ms 10392 KB Output is correct
17 Correct 309 ms 29584 KB Output is correct
18 Correct 298 ms 29620 KB Output is correct
19 Correct 340 ms 29540 KB Output is correct
20 Correct 363 ms 29764 KB Output is correct
21 Correct 1610 ms 31664 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 250 ms 8384 KB Output is correct
2 Correct 2662 ms 11508 KB Output is correct
3 Execution timed out 5096 ms 14420 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 5 ms 7368 KB Output is correct
4 Correct 5 ms 7376 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 6 ms 7500 KB Output is correct
8 Correct 8 ms 7500 KB Output is correct
9 Correct 6 ms 7448 KB Output is correct
10 Correct 6 ms 7500 KB Output is correct
11 Correct 7 ms 7500 KB Output is correct
12 Correct 7 ms 7500 KB Output is correct
13 Correct 5 ms 7496 KB Output is correct
14 Correct 6 ms 7500 KB Output is correct
15 Correct 5 ms 7544 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 5 ms 7500 KB Output is correct
18 Correct 8 ms 7500 KB Output is correct
19 Correct 111 ms 8140 KB Output is correct
20 Correct 122 ms 8236 KB Output is correct
21 Correct 77 ms 8260 KB Output is correct
22 Correct 108 ms 8568 KB Output is correct
23 Correct 164 ms 11336 KB Output is correct
24 Correct 160 ms 11496 KB Output is correct
25 Correct 225 ms 11728 KB Output is correct
26 Correct 207 ms 11956 KB Output is correct
27 Correct 5 ms 7372 KB Output is correct
28 Correct 6 ms 7372 KB Output is correct
29 Correct 28 ms 7372 KB Output is correct
30 Correct 217 ms 7684 KB Output is correct
31 Correct 1096 ms 8716 KB Output is correct
32 Correct 5 ms 7372 KB Output is correct
33 Correct 6 ms 7464 KB Output is correct
34 Correct 6 ms 7500 KB Output is correct
35 Correct 13 ms 7500 KB Output is correct
36 Correct 215 ms 7776 KB Output is correct
37 Correct 1022 ms 8860 KB Output is correct
38 Correct 17 ms 8652 KB Output is correct
39 Correct 15 ms 8652 KB Output is correct
40 Correct 18 ms 8640 KB Output is correct
41 Correct 185 ms 8772 KB Output is correct
42 Correct 1319 ms 10392 KB Output is correct
43 Correct 309 ms 29584 KB Output is correct
44 Correct 298 ms 29620 KB Output is correct
45 Correct 340 ms 29540 KB Output is correct
46 Correct 363 ms 29764 KB Output is correct
47 Correct 1610 ms 31664 KB Output is correct
48 Correct 250 ms 8384 KB Output is correct
49 Correct 2662 ms 11508 KB Output is correct
50 Execution timed out 5096 ms 14420 KB Time limit exceeded
51 Halted 0 ms 0 KB -