#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int NMAX(100005);
vector<pair<int, ll> > G[NMAX];
vector<int> frati[NMAX];
map<pair<int, int>, vector<pair<int, int> > > mp;
bool dead[NMAX], mark[NMAX], viz[NMAX];
int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
ll dist[NMAX], maxx[NMAX];
struct SEGTREE
{
vector<ll> Arb, lazy;
vector<int> in, out;
int cati, ma;
inline void init(int n)
{
cati = n;
int put = 1;
while(put <= n)
put <<= 1;
put <<= 1;
ma = put;
Arb.resize(put), in.resize(put), out.resize(put), lazy.resize(put);
}
inline void build(int nod, int st, int dr)
{
if(st == dr)
{
Arb[nod] = dist[st];
return;
}
int mij = (st + dr) / 2;
build(2 * nod, st, mij);
build(2 * nod + 1, mij + 1, dr);
Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]);
}
inline void push(int nod){
if(lazy[nod]){
if(2 * nod <= ma)
Arb[2 * nod] += lazy[nod], lazy[2 * nod] += lazy[nod];
if(2 * nod + 1 <= ma)
Arb[2 * nod + 1] += lazy[nod], lazy[2 * nod + 1] += lazy[nod];
lazy[nod] = 0;
}
}
inline void update(int nod, int st, int dr, int a, int b, ll val){
if(a <= st && dr <= b){
lazy[nod] += val;
Arb[nod] += val;
push(nod);
return;
}
push(nod);
int mij = (st + dr) / 2;
if(a <= mij)
update(2 * nod, st, mij, a, b, val);
if(b > mij)
update(2 * nod + 1, mij + 1, dr, a, b, val);
Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]);
}
inline ll query(int nod, int st, int dr, int a, int b){
if(a <= st && dr <= b)
return Arb[nod];
push(nod);
int mij = (st + dr) / 2;
ll rez1 = 0, rez2 = 0;
if(a <= mij)
rez1 = query(2 * nod, st, mij, a, b);
if(b > mij)
rez2 = query(2 * nod + 1, mij + 1, dr, a, b);
return max(rez1, rez2);
}
} interv[NMAX];
inline int getC(int nod)
{
viz[nod] = 1;
sz[nod] = 1;
int maxx = 0;
for(auto it: G[nod])
if(!viz[it.first] && mark[it.first])
{
int c = getC(it.first);
if(c != -1)
return c;
sz[nod] += sz[it.first];
maxx = max(maxx, sz[it.first]);
}
maxx = max(maxx, dim - sz[nod]);
if(maxx <= dim / 2)
return nod;
return -1;
}
inline void DFS(int nod)
{
viz[nod] = 1;
tip[nod] = cnt;
for(auto it: G[nod])
if(!viz[it.first] && mark[it.first])
DFS(it.first);
}
inline void buildTree(int nod, int tata = -1)
{
interv[baza].in[id[nod]] = ++mov;
for(auto it: G[nod])
if(tata != it.first && mark[it.first])
{
mp[ {min(it.first, nod), max(it.first, nod)}].push_back({id[it.first], baza});
dist[mov + 1] = dist[interv[baza].in[id[nod]]] + it.second;
buildTree(it.first, nod);
}
interv[baza].out[id[nod]] = mov;
}
inline void centroidDecomp(vector<int> nodes)
{
if(nodes.size() == 1)
return;
int mr = 0;
for(auto it: nodes)
mark[it] = 1, sz[it] = tip[it] = 0, viz[it] = 0, id[it] = ++mr;
dim = nodes.size();
int cen = getC(nodes[0]);
baza = cen;
mov = dist[1] = 0;
interv[baza].init(nodes.size());
buildTree(cen);
interv[baza].build(1, 1, nodes.size());
for(auto it: nodes)
viz[it] = 0;
viz[cen] = 1;
cnt = 0;
for(auto it: G[cen])
if(!viz[it.first] && mark[it.first])
{
frati[cen].push_back(id[it.first]);
++cnt;
DFS(it.first);
}
vector<vector<int> > nex(cnt + 1);
for(auto it: nodes)
nex[tip[it]].push_back(it);
for(auto it: nodes)
mark[it] = 0, sz[it] = tip[it] = 0, viz[it] = 0;
int nn = cnt;
for(int i = 1; i <= nn; ++i)
centroidDecomp(nex[i]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, q;
ll w;
cin >> n >> q >> w;
vector<tuple<int, int, ll> > Muchie;
for(int i = 1; i < n; ++i)
{
int a, b;
ll c;
cin >> a >> b >> c;
Muchie.push_back(make_tuple(min(a, b), max(a, b), c));
G[a].push_back({b, c});
G[b].push_back({a, c});
}
vector<int> noduri;
for(int i = 1; i <= n; ++i)
noduri.push_back(i);
centroidDecomp(noduri);
auto calc = [](int i)
{
vector<ll> vec;
for(auto it: frati[i])
{
ll val = interv[i].query(1, 1, interv[i].cati, interv[i].in[it], interv[i].out[it]);
vec.push_back(val);
}
sort(vec.begin(), vec.end(), greater<ll>());
ll maxxx = 0;
if(vec.size() > 1)
maxxx = vec[0] + vec[1];
else maxxx = vec[0];
return maxxx;
};
multiset<ll> s;
for(int i = 1; i <= n; ++i)
if(frati[i].size())
maxx[i] = calc(i), s.insert(-maxx[i]);
ll last = 0;
for(int i = 1; i <= q; ++i)
{
int d;
ll e;
cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % w;
int x, y;
ll c;
tie(x, y, c) = Muchie[d];
for(auto it: mp[ {x, y}]){
interv[it.second].update(1, 1, interv[it.second].cati, interv[it.second].in[it.first], interv[it.second].out[it.first], e - c);
s.erase(s.find(-maxx[it.second]));
maxx[it.second] = calc(it.second);
s.insert(-maxx[it.second]);
}
Muchie[d] = make_tuple(x, y, e);
cout << -*s.begin() << '\n';
last = -*s.begin();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
15188 KB |
Output is correct |
2 |
Correct |
9 ms |
15180 KB |
Output is correct |
3 |
Correct |
9 ms |
15180 KB |
Output is correct |
4 |
Correct |
10 ms |
15192 KB |
Output is correct |
5 |
Correct |
10 ms |
15180 KB |
Output is correct |
6 |
Correct |
10 ms |
15196 KB |
Output is correct |
7 |
Correct |
10 ms |
15180 KB |
Output is correct |
8 |
Correct |
9 ms |
15180 KB |
Output is correct |
9 |
Correct |
10 ms |
15180 KB |
Output is correct |
10 |
Correct |
13 ms |
15180 KB |
Output is correct |
11 |
Correct |
9 ms |
15180 KB |
Output is correct |
12 |
Correct |
14 ms |
15192 KB |
Output is correct |
13 |
Correct |
9 ms |
15180 KB |
Output is correct |
14 |
Correct |
13 ms |
15180 KB |
Output is correct |
15 |
Correct |
15 ms |
15180 KB |
Output is correct |
16 |
Correct |
9 ms |
15180 KB |
Output is correct |
17 |
Correct |
10 ms |
15180 KB |
Output is correct |
18 |
Correct |
9 ms |
15240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
15188 KB |
Output is correct |
2 |
Correct |
9 ms |
15180 KB |
Output is correct |
3 |
Correct |
9 ms |
15180 KB |
Output is correct |
4 |
Correct |
10 ms |
15192 KB |
Output is correct |
5 |
Correct |
10 ms |
15180 KB |
Output is correct |
6 |
Correct |
10 ms |
15196 KB |
Output is correct |
7 |
Correct |
10 ms |
15180 KB |
Output is correct |
8 |
Correct |
9 ms |
15180 KB |
Output is correct |
9 |
Correct |
10 ms |
15180 KB |
Output is correct |
10 |
Correct |
13 ms |
15180 KB |
Output is correct |
11 |
Correct |
9 ms |
15180 KB |
Output is correct |
12 |
Correct |
14 ms |
15192 KB |
Output is correct |
13 |
Correct |
9 ms |
15180 KB |
Output is correct |
14 |
Correct |
13 ms |
15180 KB |
Output is correct |
15 |
Correct |
15 ms |
15180 KB |
Output is correct |
16 |
Correct |
9 ms |
15180 KB |
Output is correct |
17 |
Correct |
10 ms |
15180 KB |
Output is correct |
18 |
Correct |
9 ms |
15240 KB |
Output is correct |
19 |
Correct |
52 ms |
15968 KB |
Output is correct |
20 |
Correct |
37 ms |
16032 KB |
Output is correct |
21 |
Correct |
46 ms |
15972 KB |
Output is correct |
22 |
Correct |
37 ms |
16076 KB |
Output is correct |
23 |
Correct |
71 ms |
19204 KB |
Output is correct |
24 |
Correct |
74 ms |
20224 KB |
Output is correct |
25 |
Correct |
96 ms |
20936 KB |
Output is correct |
26 |
Correct |
74 ms |
22112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15180 KB |
Output is correct |
2 |
Correct |
8 ms |
15180 KB |
Output is correct |
3 |
Correct |
11 ms |
15180 KB |
Output is correct |
4 |
Correct |
41 ms |
15424 KB |
Output is correct |
5 |
Correct |
151 ms |
16264 KB |
Output is correct |
6 |
Correct |
12 ms |
15180 KB |
Output is correct |
7 |
Correct |
16 ms |
15320 KB |
Output is correct |
8 |
Correct |
20 ms |
15324 KB |
Output is correct |
9 |
Correct |
108 ms |
15396 KB |
Output is correct |
10 |
Correct |
1010 ms |
15616 KB |
Output is correct |
11 |
Execution timed out |
5022 ms |
16664 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
15948 KB |
Output is correct |
2 |
Correct |
43 ms |
16088 KB |
Output is correct |
3 |
Correct |
188 ms |
16536 KB |
Output is correct |
4 |
Correct |
332 ms |
17404 KB |
Output is correct |
5 |
Correct |
44 ms |
25256 KB |
Output is correct |
6 |
Correct |
97 ms |
25436 KB |
Output is correct |
7 |
Correct |
342 ms |
25968 KB |
Output is correct |
8 |
Correct |
672 ms |
26836 KB |
Output is correct |
9 |
Correct |
223 ms |
70592 KB |
Output is correct |
10 |
Correct |
323 ms |
70732 KB |
Output is correct |
11 |
Correct |
713 ms |
71704 KB |
Output is correct |
12 |
Correct |
1203 ms |
72332 KB |
Output is correct |
13 |
Correct |
455 ms |
130940 KB |
Output is correct |
14 |
Correct |
526 ms |
130996 KB |
Output is correct |
15 |
Correct |
1094 ms |
131604 KB |
Output is correct |
16 |
Correct |
1581 ms |
132472 KB |
Output is correct |
17 |
Correct |
2885 ms |
132268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3661 ms |
130532 KB |
Output is correct |
2 |
Correct |
3483 ms |
133496 KB |
Output is correct |
3 |
Correct |
3302 ms |
132496 KB |
Output is correct |
4 |
Correct |
3352 ms |
134120 KB |
Output is correct |
5 |
Execution timed out |
5062 ms |
128440 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
15188 KB |
Output is correct |
2 |
Correct |
9 ms |
15180 KB |
Output is correct |
3 |
Correct |
9 ms |
15180 KB |
Output is correct |
4 |
Correct |
10 ms |
15192 KB |
Output is correct |
5 |
Correct |
10 ms |
15180 KB |
Output is correct |
6 |
Correct |
10 ms |
15196 KB |
Output is correct |
7 |
Correct |
10 ms |
15180 KB |
Output is correct |
8 |
Correct |
9 ms |
15180 KB |
Output is correct |
9 |
Correct |
10 ms |
15180 KB |
Output is correct |
10 |
Correct |
13 ms |
15180 KB |
Output is correct |
11 |
Correct |
9 ms |
15180 KB |
Output is correct |
12 |
Correct |
14 ms |
15192 KB |
Output is correct |
13 |
Correct |
9 ms |
15180 KB |
Output is correct |
14 |
Correct |
13 ms |
15180 KB |
Output is correct |
15 |
Correct |
15 ms |
15180 KB |
Output is correct |
16 |
Correct |
9 ms |
15180 KB |
Output is correct |
17 |
Correct |
10 ms |
15180 KB |
Output is correct |
18 |
Correct |
9 ms |
15240 KB |
Output is correct |
19 |
Correct |
52 ms |
15968 KB |
Output is correct |
20 |
Correct |
37 ms |
16032 KB |
Output is correct |
21 |
Correct |
46 ms |
15972 KB |
Output is correct |
22 |
Correct |
37 ms |
16076 KB |
Output is correct |
23 |
Correct |
71 ms |
19204 KB |
Output is correct |
24 |
Correct |
74 ms |
20224 KB |
Output is correct |
25 |
Correct |
96 ms |
20936 KB |
Output is correct |
26 |
Correct |
74 ms |
22112 KB |
Output is correct |
27 |
Correct |
9 ms |
15180 KB |
Output is correct |
28 |
Correct |
8 ms |
15180 KB |
Output is correct |
29 |
Correct |
11 ms |
15180 KB |
Output is correct |
30 |
Correct |
41 ms |
15424 KB |
Output is correct |
31 |
Correct |
151 ms |
16264 KB |
Output is correct |
32 |
Correct |
12 ms |
15180 KB |
Output is correct |
33 |
Correct |
16 ms |
15320 KB |
Output is correct |
34 |
Correct |
20 ms |
15324 KB |
Output is correct |
35 |
Correct |
108 ms |
15396 KB |
Output is correct |
36 |
Correct |
1010 ms |
15616 KB |
Output is correct |
37 |
Execution timed out |
5022 ms |
16664 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |