이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
using namespace std;
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <utility>
#include <memory.h>
#include <vector>
#include <bitset>
typedef pair<int,int> pii;
typedef long long LL;
#define iter(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#define mkp make_pair
#include <climits>
const int maxn = 1e5+10,mod = 0;
struct EDGE{
int u,v;
LL w;
int con_to(int e){
return u == e ? v : u;
}
int l,r;
EDGE(int u,int v,LL w):u(u), v(v), w(w), l(0), r(0){}
EDGE(){}
}edge[maxn];
vector <pair<int,LL>> adj[maxn];
int father[maxn];
pii seg[maxn];
LL mx[maxn];
#define mid (LB+RB)/2
struct segtree{
vector <LL> arr,mx,lazy;
segtree(){
arr.resize(1);
}
void mt(){
mx.resize(arr.size()*4);
lazy.resize(arr.size()*4);
maketree(1,1,arr.size()-1);
}
void maketree(int cur,int LB,int RB){
if (LB == RB) mx[cur] = arr[LB];
else{
maketree(cur*2,LB,mid);
maketree(cur*2+1,mid+1,RB);
mx[cur] = max(mx[cur*2],mx[cur*2+1]);
}
}
void push(int cur,int LB,int RB){
mx[cur] += lazy[cur];
if (LB != RB){
lazy[cur*2] += lazy[cur];
lazy[cur*2+1] += lazy[cur];
}
lazy[cur] = 0;
}
void ru(int l,int r,LL val,int cur,int LB,int RB){
if (l == LB and r == RB){
lazy[cur] += val;
push(cur,LB,RB);
return;
}
push(cur,LB,RB);
if (r <= mid) ru(l,r,val,cur*2,LB,mid);
else if (l > mid) ru(l,r,val,cur*2+1,mid+1,RB);
else{
ru(l,mid,val,cur*2,LB,mid);
ru(mid+1,r,val,cur*2+1,mid+1,RB);
}
mx[cur] = max(mx[cur*2],mx[cur*2+1]);
}
LL rq(int l,int r,int cur,int LB,int RB){
push(cur,LB,RB);
if (l == LB and r == RB) return mx[cur];
if (r <= mid) return rq(l,r,cur*2,LB,mid);
else if (l > mid) return rq(l,r,cur*2+1,mid+1,RB);
else return max(rq(l,mid,cur*2,LB,mid),rq(mid+1,r,cur*2+1,mid+1,RB));
}
void upd(int l,int r,LL val){
ru(l,r,val,1,1,arr.size()-1);
}
LL query(int l,int r){
return rq(l,r,1,1,arr.size()-1);
}
};
vector <segtree> st;
int belong[maxn],treecnt;
pii dfs(int x,int fr,LL dis,int sti){
father[x] = fr;
belong[x] = sti;
pii r = {};
for (auto [i,w]:adj[x]) if (i != fr){
if (!r.F) r = dfs(i,x,dis + w,sti);
else r.S = dfs(i,x,dis + w,sti).S;
}
if (!r.F){
r = mkp(int(st[sti].arr.size()),int(st[sti].arr.size()));
st[sti].arr.pb(dis);
}
seg[x] = r;
return r;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n,q,w;
cin >> n >> q >> w;
for (int i=0;i<n-1;++i){
int u,v; LL c;
cin >> u >> v >> c;
edge[i] = EDGE(u,v,c);
adj[u].pb(mkp(v,c));
adj[v].pb(mkp(u,c));
}
st.resize(adj[1].size());
multiset <LL> ms;
for (auto [i,d]:adj[1]){
dfs(i,1,d,treecnt);
st[treecnt].mt();
mx[treecnt] = st[treecnt].mx[1];
ms.insert(mx[treecnt]);
++treecnt;
}
for (int i=0;i<n-1;++i){
if (edge[i].u == father[edge[i].v])
swap(edge[i].u,edge[i].v);
}
LL last = 0;
while (q--){
LL d,e;
cin >> d >> e;
d = (last + d) % (n-1);
e = (last + e) % w;
LL dif = e - edge[d].w;
int m = edge[d].u;
edge[d].w = e;
ms.erase(ms.find(mx[belong[m]]));
st[belong[m]].upd(seg[m].F,seg[m].S,dif);
mx[belong[m]] = st[belong[m]].query(1,st[belong[m]].arr.size()-1);
ms.insert(mx[belong[m]]);
last = *prev(ms.end()) + (ms.size() > 1 ? *prev(prev(ms.end())) : 0);
cout /*<< d << ' ' << e << ' '*/ << last << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |