#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define MAX 100000
#define des first
#define p second
struct x{
lli mayor;
lli lazy;
lli hder;
lli hizq;
};
lli n,q,w,a,b,c,k,last,id,act,ult,sum,l,r;
lli peso[MAX+2];
pair<lli,lli> arr[MAX+2];
vector<pair<lli,lli> > hijos[MAX+2];
vector<lli> iniciales;
pair<lli,lli> rango[MAX+2];
vector<x> st;
multiset<lli> res;
multiset<lli>::iterator it;
lli valores[MAX+2],pertenece[MAX+2];
void recorre(lli pos, lli padre,lli prof) {
rango[pos].first = act;
if (padre == 1) pertenece[pos] = pos;
else pertenece[pos] = pertenece[padre];
bool tiene = false;
for (auto h : hijos[pos]) {
if (h.des == padre) continue;
tiene = true;
recorre(h.des,pos,prof + h.p);
}
if (!tiene) {
act++;
iniciales.push_back(prof);
}
rango[pos].second = act-1;
}
void arma(lli ini, lli fin, lli pos) {
lli mitad;
if (ini == fin) st[pos].mayor = iniciales[ini];
else {
mitad = (ini+fin)/2;
st.push_back({0,0,0,0});
st.push_back({0,0,0,0});
st[pos].hizq = ult;
st[pos].hder = ult+1;
ult += 2;
arma(ini,mitad,st[pos].hizq);
arma(mitad+1,fin,st[pos].hder);
st[pos].mayor = max(st[ st[pos].hizq ].mayor, st[ st[pos].hder ].mayor);
}
}
void aplica(lli pos) {
if (st[pos].lazy != 0) {
if (st[pos].hizq != 0) {
st[ st[pos].hizq ].lazy += st[pos].lazy;
st[ st[pos].hder ].lazy += st[pos].lazy;
}
st[pos].mayor += st[pos].lazy;
st[pos].lazy = 0;
}
}
void actualiza(lli pos, lli ini, lli fin, lli l, lli r, lli val) {
aplica(pos);
if (ini >= l && fin <= r) {
st[pos].lazy += val;
aplica(pos);
}
else if (fin < l || ini > r) return ;
else {
lli mitad = (ini+fin)/2;
actualiza(st[pos].hizq,ini,mitad,l,r,val);
actualiza(st[pos].hder,mitad+1,fin,l,r,val);
st[pos].mayor = max(st[ st[pos].hizq ].mayor, st[ st[pos].hder ].mayor);
}
}
lli query(lli pos, lli ini, lli fin, lli l, lli r) {
aplica(pos);
if (ini >= l && fin <= r) return st[pos].mayor;
else if (ini > r || fin < l) return 0;
else {
lli mitad = (ini+fin)/2;
lli a = query(st[pos].hizq, ini,mitad,l,r);
lli b = query(st[pos].hder, mitad+1,fin,l,r);
return max(a,b);
}
}
lli imprime() {
if (res.size() == 1) {
it = res.begin();
return *it;
}
else {
lli total;
auto itr = res.rbegin();
total = *itr;
itr++;
total += *itr;
return total;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q >> w;
rep(i,1,n-1) {
cin >> a >> b >> c;
arr[i] = {a,b};
peso[i] = c;
hijos[a].push_back({b,c});
hijos[b].push_back({a,c});
}
act = 1;
iniciales.push_back(0);
recorre(1,0,0);
act--;
st.push_back({0,0,0,0});
ult = 1;
arma(1,act,0);
for (auto h : hijos[1]) {
valores[h.des] = query(0,1,act,rango[h.des].first,rango[h.des].second);
res.insert(valores[h.des]);
}
rep(i,1,q) {
//correcto
cin >> id >> c;
id += last;
id %= (n-1);
id++;
c += last;
c %= w;
a = arr[id].first;
b = arr[id].second;
//fill
sum = c - peso[id];
peso[id] = c;
l = max(rango[a].first, rango[b].first);
r = min(rango[a].second, rango[b].second);
if (pertenece[a] != 0) k = pertenece[a];
else k = pertenece[b];
it = res.lower_bound(valores[k]);
res.erase(it);
actualiza(0,1,act,l,r,sum);
valores[k] = query(0,1,act,rango[k].first,rango[k].second);
res.insert(valores[k]);
//last = resultado
last = imprime();
cout << last << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
3 ms |
2700 KB |
Output is correct |
4 |
Correct |
13 ms |
2820 KB |
Output is correct |
5 |
Correct |
58 ms |
3716 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2764 KB |
Output is correct |
8 |
Correct |
2 ms |
2764 KB |
Output is correct |
9 |
Correct |
4 ms |
2764 KB |
Output is correct |
10 |
Correct |
19 ms |
3024 KB |
Output is correct |
11 |
Correct |
85 ms |
4036 KB |
Output is correct |
12 |
Correct |
6 ms |
3912 KB |
Output is correct |
13 |
Correct |
6 ms |
3856 KB |
Output is correct |
14 |
Correct |
9 ms |
3848 KB |
Output is correct |
15 |
Correct |
28 ms |
4128 KB |
Output is correct |
16 |
Correct |
117 ms |
5232 KB |
Output is correct |
17 |
Correct |
119 ms |
25804 KB |
Output is correct |
18 |
Correct |
115 ms |
25760 KB |
Output is correct |
19 |
Correct |
119 ms |
25760 KB |
Output is correct |
20 |
Correct |
162 ms |
26084 KB |
Output is correct |
21 |
Correct |
372 ms |
27412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
2764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
212 ms |
17184 KB |
Output is correct |
2 |
Correct |
241 ms |
21240 KB |
Output is correct |
3 |
Correct |
238 ms |
21292 KB |
Output is correct |
4 |
Correct |
260 ms |
22356 KB |
Output is correct |
5 |
Correct |
267 ms |
22692 KB |
Output is correct |
6 |
Correct |
309 ms |
26072 KB |
Output is correct |
7 |
Correct |
212 ms |
23152 KB |
Output is correct |
8 |
Correct |
234 ms |
23180 KB |
Output is correct |
9 |
Correct |
271 ms |
23216 KB |
Output is correct |
10 |
Correct |
288 ms |
23896 KB |
Output is correct |
11 |
Correct |
286 ms |
24620 KB |
Output is correct |
12 |
Correct |
306 ms |
27260 KB |
Output is correct |
13 |
Correct |
145 ms |
24340 KB |
Output is correct |
14 |
Correct |
152 ms |
24376 KB |
Output is correct |
15 |
Correct |
153 ms |
24432 KB |
Output is correct |
16 |
Correct |
180 ms |
25324 KB |
Output is correct |
17 |
Correct |
204 ms |
25756 KB |
Output is correct |
18 |
Correct |
231 ms |
27644 KB |
Output is correct |
19 |
Correct |
135 ms |
24400 KB |
Output is correct |
20 |
Correct |
139 ms |
24524 KB |
Output is correct |
21 |
Correct |
145 ms |
24520 KB |
Output is correct |
22 |
Correct |
181 ms |
25272 KB |
Output is correct |
23 |
Correct |
202 ms |
25656 KB |
Output is correct |
24 |
Correct |
226 ms |
27600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |