#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi," ",x.se);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
//===================//
// Added libraries //
//===================//
//===================//
//end added libraries//
//===================//
void program();
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
program();
}
//===================//
// begin program //
//===================//
const int MX = 2e5;
int n, q;
ll w, last=0;
map<ii,int> edgeN;
set<int> adj[MX];
int a[MX], b[MX]; ll c[MX];
int SZ[MX];
vll SEG[MX], LAZY[MX];
int cdN[MX];
viii infl[MX];
int bg[MX], ed[MX], curbg, curSeg;
vii segAreas[MX];
map<ll,int> SEGCNT[MX];
vll SEGT, LAZYT;
void setSeg(vll& SEG, vll& LAZY, int i, ll v, ll lazy=0, int p=0, int l=0, int r=-1) {
if(r == -1) r = SEG.sz/4-1;
SEG [p] += lazy;
LAZY[p] += lazy;
if(i < l || i > r) return;
if(l == r) {
SEG [p] = v;
return;
}
int m=(l+r)/2;
setSeg(SEG,LAZY,i,v,LAZY[p],p*2+1,l,m);
setSeg(SEG,LAZY,i,v,LAZY[p],p*2+2,m+1,r);
SEG [p] = max(SEG[p*2+1], SEG[p*2+2]);
LAZY[p] = 0;
}
void addSeg(vll& SEG, vll& LAZY, int i, int j, ll v, ll lazy=0, int p=0, int l=0, int r=-1) {
if(r == -1) r = SEG.sz/4-1;
SEG [p] += lazy;
LAZY[p] += lazy;
if(j < l || i > r) return;
if(i <= l && j >= r) {
SEG [p] += v;
LAZY[p] += v;
return;
}
int m=(l+r)/2;
addSeg(SEG,LAZY,i,j,v,LAZY[p],p*2+1,l,m);
addSeg(SEG,LAZY,i,j,v,LAZY[p],p*2+2,m+1,r);
SEG [p] = max(SEG[p*2+1], SEG[p*2+2]);
LAZY[p] = 0;
}
ll getSeg(vll& SEG, vll& LAZY, int i, int j, ll lazy=0, int p=0, int l=0, int r=-1) {
if(r == -1) r = SEG.sz/4-1;
SEG [p] += lazy;
LAZY[p] += lazy;
if(j < l || i > r) return -1e18;
if(i <= l && j >= r) return SEG[p];
int m=(l+r)/2;
ll a = getSeg(SEG,LAZY,i,j,LAZY[p],p*2+1,l,m);
ll b = getSeg(SEG,LAZY,i,j,LAZY[p],p*2+2,m+1,r);
LAZY[p] = 0;
return max(a,b);
}
void dfsSZ(int u, int p=-1) {
SZ[u] = 1;
FOR(v,adj[u]) if(v!=p) dfsSZ(v,u), SZ[u]+=SZ[v];
}
int dfsCent(int u, int p, int tot) {
FOR(v,adj[u]) if(v!=p && SZ[v] > tot/2) return dfsCent(v,u,tot);
return u;
}
int findCentroid(int u) {
dfsSZ(u);
return dfsCent(u,-1,SZ[u]);
}
void remove(int u) {
for(int v:adj[u]) adj[v].erase(u);
adj[u].clear();
}
void dfsBG(int u, int p=-1) {
bg[u] = curbg++;
FOR(v,adj[u]) if(v!=p) {
dfsBG(v,u);
int e = edgeN[{u,v}];
infl[e].pb({curSeg,bg[v],ed[v]});
addSeg(SEG[curSeg], LAZY[curSeg], bg[v], ed[v], c[e]);
if(u == curSeg) {
segAreas[u].pb({bg[v],ed[v]});
}
}
ed[u] = curbg-1;
}
void updateSeg(int u) {
ll res=0, used=0;
auto it = SEGCNT[u].end();
while(used<2) {
if(it == SEGCNT[u].begin()) break;
it--;
if(used == 1 || it->se == 1) {
res += it->fi;
} else {
res += it->fi*2ll;
}
used += it->se;
}
setSeg(SEGT,LAZYT,u,res);
}
void createSeg(int u) {
dfsSZ(u);
cdN[u] = SZ[u];
SEG [u].assign(cdN[u]*4, 0);
LAZY[u].assign(cdN[u]*4, 0);
curbg=0;
curSeg=u;
dfsBG(u);
FOR(p,segAreas[u]) SEGCNT[u][getSeg(SEG[u],LAZY[u],p.fi,p.se)]++;
updateSeg(u);
}
void centDe(int u) {
int cent = findCentroid(u);
set<int> temp = adj[cent];
createSeg(cent);
remove(cent);
FOR(v,temp) centDe(v);
}
void program() {
IN(n,q,w);
RE1(i,n-1) {
IN(a[i],b[i],c[i]);
adj[a[i]].insert(b[i]);
adj[b[i]].insert(a[i]);
edgeN[{a[i],b[i]}] = i;
edgeN[{b[i],a[i]}] = i;
}
SEGT.resize((n+1)*4);
LAZYT.resize((n+1)*4);
centDe(1);
RE(queryNumber,q) {
ll d, e; IN(d,e);
d = (d+last)%(n-1); d++;
e = (e+last)%w;
FOR(p,infl[d]) {
int bgs, eds;
tie(curSeg, bgs, eds) = p;
ii p2 = *(--lower_bound(all(segAreas[curSeg]), ii{bgs,INF}));
ll gsres = getSeg(SEG[curSeg],LAZY[curSeg],p2.fi,p2.se);
if(--SEGCNT[curSeg][gsres] == 0) SEGCNT[curSeg].erase(gsres);
addSeg(SEG[curSeg], LAZY[curSeg], bgs, eds, -c[d]);
addSeg(SEG[curSeg], LAZY[curSeg], bgs, eds, e);
SEGCNT[curSeg][getSeg(SEG[curSeg],LAZY[curSeg],p2.fi,p2.se)]++;
updateSeg(curSeg);
}
c[d] = e;
last = getSeg(SEGT,LAZYT,0,n);
OUTL(last);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
38016 KB |
Output is correct |
2 |
Correct |
23 ms |
37888 KB |
Output is correct |
3 |
Correct |
25 ms |
37880 KB |
Output is correct |
4 |
Correct |
23 ms |
38008 KB |
Output is correct |
5 |
Correct |
22 ms |
37888 KB |
Output is correct |
6 |
Correct |
23 ms |
37888 KB |
Output is correct |
7 |
Correct |
23 ms |
38016 KB |
Output is correct |
8 |
Correct |
23 ms |
38016 KB |
Output is correct |
9 |
Correct |
23 ms |
38008 KB |
Output is correct |
10 |
Correct |
24 ms |
38016 KB |
Output is correct |
11 |
Correct |
24 ms |
38016 KB |
Output is correct |
12 |
Correct |
23 ms |
38016 KB |
Output is correct |
13 |
Correct |
24 ms |
38016 KB |
Output is correct |
14 |
Correct |
25 ms |
38144 KB |
Output is correct |
15 |
Correct |
23 ms |
38016 KB |
Output is correct |
16 |
Correct |
23 ms |
38016 KB |
Output is correct |
17 |
Correct |
23 ms |
38008 KB |
Output is correct |
18 |
Correct |
23 ms |
38016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
38016 KB |
Output is correct |
2 |
Correct |
23 ms |
37888 KB |
Output is correct |
3 |
Correct |
25 ms |
37880 KB |
Output is correct |
4 |
Correct |
23 ms |
38008 KB |
Output is correct |
5 |
Correct |
22 ms |
37888 KB |
Output is correct |
6 |
Correct |
23 ms |
37888 KB |
Output is correct |
7 |
Correct |
23 ms |
38016 KB |
Output is correct |
8 |
Correct |
23 ms |
38016 KB |
Output is correct |
9 |
Correct |
23 ms |
38008 KB |
Output is correct |
10 |
Correct |
24 ms |
38016 KB |
Output is correct |
11 |
Correct |
24 ms |
38016 KB |
Output is correct |
12 |
Correct |
23 ms |
38016 KB |
Output is correct |
13 |
Correct |
24 ms |
38016 KB |
Output is correct |
14 |
Correct |
25 ms |
38144 KB |
Output is correct |
15 |
Correct |
23 ms |
38016 KB |
Output is correct |
16 |
Correct |
23 ms |
38016 KB |
Output is correct |
17 |
Correct |
23 ms |
38008 KB |
Output is correct |
18 |
Correct |
23 ms |
38016 KB |
Output is correct |
19 |
Correct |
59 ms |
38912 KB |
Output is correct |
20 |
Correct |
62 ms |
38912 KB |
Output is correct |
21 |
Correct |
67 ms |
39040 KB |
Output is correct |
22 |
Correct |
76 ms |
39160 KB |
Output is correct |
23 |
Correct |
100 ms |
42488 KB |
Output is correct |
24 |
Correct |
124 ms |
43384 KB |
Output is correct |
25 |
Correct |
151 ms |
43896 KB |
Output is correct |
26 |
Correct |
133 ms |
44664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
37880 KB |
Output is correct |
2 |
Correct |
24 ms |
38016 KB |
Output is correct |
3 |
Correct |
26 ms |
38016 KB |
Output is correct |
4 |
Correct |
42 ms |
38144 KB |
Output is correct |
5 |
Correct |
121 ms |
39160 KB |
Output is correct |
6 |
Correct |
24 ms |
37888 KB |
Output is correct |
7 |
Correct |
24 ms |
38144 KB |
Output is correct |
8 |
Correct |
24 ms |
38144 KB |
Output is correct |
9 |
Correct |
27 ms |
38272 KB |
Output is correct |
10 |
Correct |
55 ms |
38520 KB |
Output is correct |
11 |
Correct |
184 ms |
39544 KB |
Output is correct |
12 |
Correct |
38 ms |
40440 KB |
Output is correct |
13 |
Correct |
38 ms |
40440 KB |
Output is correct |
14 |
Correct |
39 ms |
40440 KB |
Output is correct |
15 |
Correct |
80 ms |
40696 KB |
Output is correct |
16 |
Correct |
246 ms |
41976 KB |
Output is correct |
17 |
Correct |
361 ms |
85552 KB |
Output is correct |
18 |
Correct |
356 ms |
85464 KB |
Output is correct |
19 |
Correct |
364 ms |
85744 KB |
Output is correct |
20 |
Correct |
411 ms |
85868 KB |
Output is correct |
21 |
Correct |
706 ms |
87148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
38912 KB |
Output is correct |
2 |
Correct |
83 ms |
39080 KB |
Output is correct |
3 |
Correct |
323 ms |
39804 KB |
Output is correct |
4 |
Correct |
594 ms |
40440 KB |
Output is correct |
5 |
Correct |
102 ms |
50556 KB |
Output is correct |
6 |
Correct |
186 ms |
50680 KB |
Output is correct |
7 |
Correct |
582 ms |
51320 KB |
Output is correct |
8 |
Correct |
1069 ms |
52176 KB |
Output is correct |
9 |
Correct |
500 ms |
108408 KB |
Output is correct |
10 |
Correct |
627 ms |
108700 KB |
Output is correct |
11 |
Correct |
1161 ms |
109304 KB |
Output is correct |
12 |
Correct |
1901 ms |
110328 KB |
Output is correct |
13 |
Correct |
1028 ms |
185156 KB |
Output is correct |
14 |
Correct |
1175 ms |
185572 KB |
Output is correct |
15 |
Correct |
1848 ms |
186260 KB |
Output is correct |
16 |
Correct |
2665 ms |
187044 KB |
Output is correct |
17 |
Correct |
3790 ms |
186744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4404 ms |
164816 KB |
Output is correct |
2 |
Correct |
4561 ms |
167532 KB |
Output is correct |
3 |
Correct |
4584 ms |
166968 KB |
Output is correct |
4 |
Correct |
4569 ms |
167604 KB |
Output is correct |
5 |
Correct |
4456 ms |
161036 KB |
Output is correct |
6 |
Correct |
3954 ms |
129960 KB |
Output is correct |
7 |
Execution timed out |
5061 ms |
191548 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
38016 KB |
Output is correct |
2 |
Correct |
23 ms |
37888 KB |
Output is correct |
3 |
Correct |
25 ms |
37880 KB |
Output is correct |
4 |
Correct |
23 ms |
38008 KB |
Output is correct |
5 |
Correct |
22 ms |
37888 KB |
Output is correct |
6 |
Correct |
23 ms |
37888 KB |
Output is correct |
7 |
Correct |
23 ms |
38016 KB |
Output is correct |
8 |
Correct |
23 ms |
38016 KB |
Output is correct |
9 |
Correct |
23 ms |
38008 KB |
Output is correct |
10 |
Correct |
24 ms |
38016 KB |
Output is correct |
11 |
Correct |
24 ms |
38016 KB |
Output is correct |
12 |
Correct |
23 ms |
38016 KB |
Output is correct |
13 |
Correct |
24 ms |
38016 KB |
Output is correct |
14 |
Correct |
25 ms |
38144 KB |
Output is correct |
15 |
Correct |
23 ms |
38016 KB |
Output is correct |
16 |
Correct |
23 ms |
38016 KB |
Output is correct |
17 |
Correct |
23 ms |
38008 KB |
Output is correct |
18 |
Correct |
23 ms |
38016 KB |
Output is correct |
19 |
Correct |
59 ms |
38912 KB |
Output is correct |
20 |
Correct |
62 ms |
38912 KB |
Output is correct |
21 |
Correct |
67 ms |
39040 KB |
Output is correct |
22 |
Correct |
76 ms |
39160 KB |
Output is correct |
23 |
Correct |
100 ms |
42488 KB |
Output is correct |
24 |
Correct |
124 ms |
43384 KB |
Output is correct |
25 |
Correct |
151 ms |
43896 KB |
Output is correct |
26 |
Correct |
133 ms |
44664 KB |
Output is correct |
27 |
Correct |
26 ms |
37880 KB |
Output is correct |
28 |
Correct |
24 ms |
38016 KB |
Output is correct |
29 |
Correct |
26 ms |
38016 KB |
Output is correct |
30 |
Correct |
42 ms |
38144 KB |
Output is correct |
31 |
Correct |
121 ms |
39160 KB |
Output is correct |
32 |
Correct |
24 ms |
37888 KB |
Output is correct |
33 |
Correct |
24 ms |
38144 KB |
Output is correct |
34 |
Correct |
24 ms |
38144 KB |
Output is correct |
35 |
Correct |
27 ms |
38272 KB |
Output is correct |
36 |
Correct |
55 ms |
38520 KB |
Output is correct |
37 |
Correct |
184 ms |
39544 KB |
Output is correct |
38 |
Correct |
38 ms |
40440 KB |
Output is correct |
39 |
Correct |
38 ms |
40440 KB |
Output is correct |
40 |
Correct |
39 ms |
40440 KB |
Output is correct |
41 |
Correct |
80 ms |
40696 KB |
Output is correct |
42 |
Correct |
246 ms |
41976 KB |
Output is correct |
43 |
Correct |
361 ms |
85552 KB |
Output is correct |
44 |
Correct |
356 ms |
85464 KB |
Output is correct |
45 |
Correct |
364 ms |
85744 KB |
Output is correct |
46 |
Correct |
411 ms |
85868 KB |
Output is correct |
47 |
Correct |
706 ms |
87148 KB |
Output is correct |
48 |
Correct |
32 ms |
38912 KB |
Output is correct |
49 |
Correct |
83 ms |
39080 KB |
Output is correct |
50 |
Correct |
323 ms |
39804 KB |
Output is correct |
51 |
Correct |
594 ms |
40440 KB |
Output is correct |
52 |
Correct |
102 ms |
50556 KB |
Output is correct |
53 |
Correct |
186 ms |
50680 KB |
Output is correct |
54 |
Correct |
582 ms |
51320 KB |
Output is correct |
55 |
Correct |
1069 ms |
52176 KB |
Output is correct |
56 |
Correct |
500 ms |
108408 KB |
Output is correct |
57 |
Correct |
627 ms |
108700 KB |
Output is correct |
58 |
Correct |
1161 ms |
109304 KB |
Output is correct |
59 |
Correct |
1901 ms |
110328 KB |
Output is correct |
60 |
Correct |
1028 ms |
185156 KB |
Output is correct |
61 |
Correct |
1175 ms |
185572 KB |
Output is correct |
62 |
Correct |
1848 ms |
186260 KB |
Output is correct |
63 |
Correct |
2665 ms |
187044 KB |
Output is correct |
64 |
Correct |
3790 ms |
186744 KB |
Output is correct |
65 |
Correct |
4404 ms |
164816 KB |
Output is correct |
66 |
Correct |
4561 ms |
167532 KB |
Output is correct |
67 |
Correct |
4584 ms |
166968 KB |
Output is correct |
68 |
Correct |
4569 ms |
167604 KB |
Output is correct |
69 |
Correct |
4456 ms |
161036 KB |
Output is correct |
70 |
Correct |
3954 ms |
129960 KB |
Output is correct |
71 |
Execution timed out |
5061 ms |
191548 KB |
Time limit exceeded |
72 |
Halted |
0 ms |
0 KB |
- |