답안 #467672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467672	2021-08-24T00:53:08 Z	ivan_tudor	Dynamic Diameter (CEOI19_diameter)	C++14	11 / 100	5000 ms	12716 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;
}
priority_queue<pair<long long, pair<int, int>>> best[N];
long long cval[LOGN][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].push({0, {number, centro}});
    }
  }
  bs[centro] = 0;
  bsum.push({bs[centro], centro});
  wasC[centro] = true;
  for(auto x:gr[centro]){
    if(wasC[x] == false)
      centro_dec(x, number + 1, id);
  }

}
int L, R;
long long sumbig2(priority_queue<pair<long long, pair<int, int>>> best){
  long long sum =0;
  while(best.size() && cval[best.top().second.first][best.top().second.second] != best.top().first)
    best.pop();
  if(best.empty())
    return sum;
  sum += best.top().first;
  auto mx = best.top();
  best.pop();
  cval[mx.second.first][mx.second.second] = -1;
  while(best.size() && cval[best.top().second.first][best.top().second.second] != best.top().first)
    best.pop();
  if(best.empty()){
    best.push(mx);
    cval[mx.second.first][mx.second.second] = mx.first;
    return sum;
  }
  sum += best.top().first;
  best.push(mx);
  cval[mx.second.first][mx.second.second] = mx.first;
  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 = cval[number][fs];

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

    cval[number][fs] = new_big;
    best[centro].push({new_big, {number, fs}});

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

Compilation message

diameter.cpp: In function 'void update_edge(int, int, long long int)':
diameter.cpp:147:15: warning: unused variable 'old_big' [-Wunused-variable]
  147 |     long long old_big = cval[number][fs];
      |               ^~~~~~~

Subtask #1

11.0 / 11.0

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

Subtask #2

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5964 KB	Output is correct
2	Correct	4 ms	5964 KB	Output is correct
3	Correct	4 ms	5964 KB	Output is correct
4	Correct	4 ms	5964 KB	Output is correct
5	Correct	4 ms	5964 KB	Output is correct
6	Correct	4 ms	5964 KB	Output is correct
7	Correct	4 ms	5964 KB	Output is correct
8	Correct	4 ms	5964 KB	Output is correct
9	Correct	5 ms	5964 KB	Output is correct
10	Correct	4 ms	5964 KB	Output is correct
11	Correct	4 ms	5964 KB	Output is correct
12	Correct	4 ms	5964 KB	Output is correct
13	Correct	5 ms	5964 KB	Output is correct
14	Correct	4 ms	5964 KB	Output is correct
15	Correct	5 ms	5964 KB	Output is correct
16	Correct	5 ms	5964 KB	Output is correct
17	Correct	5 ms	6092 KB	Output is correct
18	Correct	5 ms	6092 KB	Output is correct
19	Correct	2083 ms	7488 KB	Output is correct
20	Correct	2293 ms	7580 KB	Output is correct
21	Correct	2775 ms	8212 KB	Output is correct
22	Correct	2573 ms	9212 KB	Output is correct
23	Correct	4353 ms	11748 KB	Output is correct
24	Execution timed out	5067 ms	12716 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #3

0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5836 KB	Output is correct
2	Correct	4 ms	5836 KB	Output is correct
3	Correct	70 ms	5976 KB	Output is correct
4	Execution timed out	5060 ms	6660 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	161 ms	7052 KB	Output is correct
2	Execution timed out	5072 ms	8112 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5

0 / 24.0

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

Subtask #6

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5964 KB	Output is correct
2	Correct	4 ms	5964 KB	Output is correct
3	Correct	4 ms	5964 KB	Output is correct
4	Correct	4 ms	5964 KB	Output is correct
5	Correct	4 ms	5964 KB	Output is correct
6	Correct	4 ms	5964 KB	Output is correct
7	Correct	4 ms	5964 KB	Output is correct
8	Correct	4 ms	5964 KB	Output is correct
9	Correct	5 ms	5964 KB	Output is correct
10	Correct	4 ms	5964 KB	Output is correct
11	Correct	4 ms	5964 KB	Output is correct
12	Correct	4 ms	5964 KB	Output is correct
13	Correct	5 ms	5964 KB	Output is correct
14	Correct	4 ms	5964 KB	Output is correct
15	Correct	5 ms	5964 KB	Output is correct
16	Correct	5 ms	5964 KB	Output is correct
17	Correct	5 ms	6092 KB	Output is correct
18	Correct	5 ms	6092 KB	Output is correct
19	Correct	2083 ms	7488 KB	Output is correct
20	Correct	2293 ms	7580 KB	Output is correct
21	Correct	2775 ms	8212 KB	Output is correct
22	Correct	2573 ms	9212 KB	Output is correct
23	Correct	4353 ms	11748 KB	Output is correct
24	Execution timed out	5067 ms	12716 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-