| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 697207 | NintsiChkhaidze | Dynamic Diameter (CEOI19_diameter) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define pb push_back
#define pii pair<int,int>
#define s second
#define f first
#define int ll // ?
using namespace std;
const int N = 5005,M=5005,inf=1e18; // ?
vector <pii> v[N];
vector <int> comp[M];
multiset <int> st[M];
int vis[N],xi[N],yi[N],wi[N];
int id,cnt,n,centroid,CH;
int tin[M][N],tout[M][N],PAR[M][N],dep[M][N];
int t[M][4*N],add[M][4*N];
void push(int k,int h){
if (add[k][h] == 0) return;
add[k][h*2] += add[k][h];
t[k][h*2] += add[k][h];
add[k][h*2+1] += add[k][h];
t[k][h*2+1] += add[k][h];
add[k][h] = 0;
}
void upd(int k,int h,int l,int r,int L,int R,int val){
if (r < L || R < l) return;
if (L <= l && r <= R){
t[k][h] += val;
add[k][h] += val;
return;
}
push(k,h);
upd(k,left,L,R,val);
upd(k,right,L,R,val);
t[k][h] = max(t[k][h*2],t[k][h*2+1]);
}
int get(int k,int h,int l,int r,int L,int R){
if (r < L || R < l) return 0;
if (L <= l && r <= R) return t[k][h];
push(k,h);
return max(get(k,left,L,R),get(k,right,L,R));
}
int dfs(int x,int par,int root,int m){
int s = 1;
for (auto [to,idx]: v[x])
if (to != par && !vis[to]) s += dfs(to,x,root, m);
if (centroid == -1 && (x == root || s*2 >= m)) centroid = x;
return s;
}
void DFS(int x,int par){
tin[id][x] = ++cnt;
comp[id].pb(x);
PAR[id][x] = CH;
for (auto [to,q]: v[x]){
if (to == par || vis[to]) continue;
dep[id][to] = dep[id][x] + 1;
if (dep[id][x] == 1) CH = to;
DFS(to,x);
upd(id,1,1,n,tin[id][to],tout[id][to],+wi[q]);
if (dep[id][x] == 1) st[id].insert(get(id,1,1,n,tin[id][to],tout[id][to]));
}
tout[id][x] = cnt;
}
void C(int x,int m){
centroid = -1;
dfs(x, x, x, m);
vis[centroid] = 1;
++id; cnt=0;
dep[id][centroid] = 1;
DFS(centroid,centroid);
for (auto [to,idx]: v[centroid])
if (!vis[to]) C(to,m/2);
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int q,W;
cin>>n>>q>>W;
for (int i = 1; i < n; i++){
cin>>xi[i]>>yi[i]>>wi[i];
v[xi[i]].pb({yi[i],i});
v[yi[i]].pb({xi[i],i});
}
C(1,n);
int last=0;
while (q--){
int d,len;
cin>>d>>len;
d = (d + last)%(n-1) + 1;
len = (len + last)%W;
int x = xi[d],y =yi[d],delta = len - wi[d];
wi[d] = len;
for (int i = 1; i <= id; i++){
if (comp[i].size()<2 || !dep[i][x] || !dep[i][y]) continue;
if (!dep[i][x] || (dep[i][x] < dep[i][y])){
int parent = PAR[i][y];
st[i].erase(st[i].find(get(i,1,1,n,tin[i][parent],tout[i][parent])));
upd(i,1,1,n,tin[i][y],tout[i][y],delta);
st[i].insert(get(i,1,1,n,tin[i][parent],tout[i][parent]));
}
else if (!dep[i][y] || (dep[i][y] < dep[i][x])){
int parent = PAR[i][x];
st[i].erase(st[i].find(get(i,1,1,n,tin[i][parent],tout[i][parent])));
upd(i,1,1,n,tin[i][x],tout[i][x],delta);
st[i].insert(get(i,1,1,n,tin[i][parent],tout[i][parent]));
}
}
int ans1=0;
for (int i = 1; i <= id; i++){
if (!st[i].size()) continue;
int ans=0;
if (st[i].size() == 1) ans=*st[i].begin();
else {
multiset <int> :: iterator it = --st[i].end(); --it;
ans = *(--st[i].end()) + *it;
}
ans1=max(ans1,ans);
}
cout<<ans1<<"\n";
last=ans1;
}
}