#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;
const int NMAX = 1e5;
struct data_t{
int tree_id;
int st;
int dr;
int father;
bool operator < (const data_t &other)const{
if(tree_id != other.tree_id){
return tree_id < other.tree_id;
}
if(st != other.st){
return st < other.st;
}
if(dr != other.dr){
return dr < other.dr;
}
return father < other.father;
}
};
class SegTree{
int n;
vector <long long> aint;
vector <long long> lazy;
void propag(int nod,int st,int dr){
if(lazy[nod] == 0 || st == dr){
return ;
}
aint[nod * 2] += lazy[nod];
lazy[nod * 2] += lazy[nod];
aint[nod * 2 + 1] += lazy[nod];
lazy[nod * 2 + 1] += lazy[nod];
lazy[nod] = 0;
}
void update(int nod,int st,int dr,int l,int r,long long delta){
propag(nod,st,dr);
if(dr < l || st > r){
return ;
}
if(l <= st && dr <= r){
aint[nod] += delta;
lazy[nod] += delta;
return ;
}
int mid = (st + dr) / 2;
update(nod * 2,st,mid,l,r,delta);
update(nod * 2 + 1,mid + 1,dr,l,r,delta);
aint[nod] = max(aint[nod * 2],aint[nod * 2 + 1]);
}
public:
SegTree(int n){
this->n = n;
aint = vector<long long>(4 * n + 1,0);
lazy = vector<long long>(4 * n + 1,0);
}
void update(int l,int r,long long val){
update(1,1,n,l,r,val);
}
long long query(){
return aint[1];
}
};
int n,q;
long long w;
bool viz[NMAX + 5];
int weight[NMAX + 5];
vector<int> graph[NMAX + 5];
pair<int,int> edge[NMAX + 5];
long long cost[NMAX + 5];
class RootPathSolver{
int lst;
int root;
vector< SegTree > trees;
unordered_map<int,data_t> stuff;
set<pair<long long,int> > answers;//(best path,tree id)
void dfs(int nod,int tata,int id){
data_t tmp = {id,++lst,-1,tata};
weight[nod] = 1;
for(auto it:graph[nod]){
if(it == tata || viz[it] == true){
continue;
}
dfs(it,nod,id);
weight[nod] += weight[it];
}
tmp.dr = lst;
stuff[nod] = tmp;
}
public:
RootPathSolver(){
}
RootPathSolver(int root){
this->root = root;
int lst_id = -1;
for(auto it:graph[root]){
if(viz[it] == false){
lst = 0;
dfs(it,root,++lst_id);
trees.push_back(SegTree(weight[it]));
answers.insert({0,it});
}
}
}
void update(pair<int,int> edge,long long delta){
data_t tmp = stuff[edge.second];
if(edge.second == root || tmp.father != edge.first){
swap(edge.second,edge.first);
tmp = stuff[edge.second];
}
answers.erase({trees[tmp.tree_id].query(),tmp.tree_id});
trees[tmp.tree_id].update(tmp.st,tmp.dr,delta);
answers.insert({trees[tmp.tree_id].query(),tmp.tree_id});
}
long long query(){
if(answers.empty()){
return 0;
}
else if(answers.size() == 1){
return answers.rbegin()->first;
}
else{
return (answers.rbegin())->first + (next(answers.rbegin()))->first;
}
}
};
class Centroid{
public:
int root;
vector<RootPathSolver> chestie;
vector<vector<int> > history;
set<pair<long long,int> > answers;
void dfs(int nod,int tata){
weight[nod] = 1;
for(auto it:graph[nod]){
if(it == tata || viz[it] == true){
continue;
}
dfs(it,nod);
weight[nod] += weight[it];
}
}
void dfs_root(int nod,int tata,int root){
if(root != nod){
history[nod].push_back(root);
}
for(auto it:graph[nod]){
if(viz[it] == true || it == tata){
continue;
}
dfs_root(it,nod,root);
}
}
int centroid(int nod){
dfs(nod,0);
int total_weight = weight[nod];
int root = nod;
while(true){
int bst = -1;
for(auto it:graph[root]){
if(viz[it] == true || it == nod){
continue;
}
if(bst == -1 || weight[it] > weight[bst]){
bst = it;
}
}
if(bst != -1 && weight[bst] * 2 > total_weight){
nod = root;
root = bst;
}
else{
break;
}
}
viz[root] = true;
chestie[root] = RootPathSolver(root);
dfs_root(root,0,root);
answers.insert({0,root});
for(auto it:graph[root]){
if(viz[it] == false){
int tmp = centroid(it);
}
}
return root;
}
public:
Centroid(int n){
this->chestie = vector<RootPathSolver>(n + 1,RootPathSolver());
this->history = vector<vector<int>>(n + 1,vector<int>());;
this->root = centroid(1);
}
void update(pair<int,int> edge,long long delta){
if(history[edge.first].size() > history[edge.second].size()){
swap(edge.first,edge.second);
}
for(auto it:history[edge.second]){
answers.erase({chestie[it].query(),it});
chestie[it].update(edge,delta);
answers.insert({chestie[it].query(),it});
}
}
long long query(){
return answers.rbegin()->first;
}
};
int main(){
scanf("%d %d %lld",&n,&q,&w);
for(int i = 1;i < n;i++){
scanf("%d %d %lld",&edge[i].first,&edge[i].second,&cost[i]);
graph[edge[i].first].push_back(edge[i].second);
graph[edge[i].second].push_back(edge[i].first);
}
Centroid a(n);
for(int i = 1;i < n;i++){
a.update(edge[i],cost[i]);
}
long long last = 0;
while(q--){
int d;
long long e;
scanf("%d %lld",&d,&e);
d = (d + last) % (n - 1) + 1;
e = (e + last) % w;
a.update(edge[d],e - cost[d]);
cost[d] = e;
last = a.query();
printf("%lld\n",last);
}
return 0;
}
Compilation message
diameter.cpp: In member function 'int Centroid::centroid(int)':
diameter.cpp:228:21: warning: unused variable 'tmp' [-Wunused-variable]
int tmp = centroid(it);
^~~
diameter.cpp: In function 'int main()':
diameter.cpp:261:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&n,&q,&w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:264:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&edge[i].first,&edge[i].second,&cost[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:282:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %lld",&d,&e);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2680 KB |
Output is correct |
2 |
Correct |
6 ms |
2680 KB |
Output is correct |
3 |
Correct |
6 ms |
2680 KB |
Output is correct |
4 |
Correct |
6 ms |
2680 KB |
Output is correct |
5 |
Correct |
6 ms |
2680 KB |
Output is correct |
6 |
Correct |
6 ms |
2680 KB |
Output is correct |
7 |
Correct |
6 ms |
2680 KB |
Output is correct |
8 |
Correct |
7 ms |
2680 KB |
Output is correct |
9 |
Correct |
6 ms |
2680 KB |
Output is correct |
10 |
Correct |
6 ms |
2680 KB |
Output is correct |
11 |
Correct |
6 ms |
2680 KB |
Output is correct |
12 |
Correct |
6 ms |
2680 KB |
Output is correct |
13 |
Correct |
7 ms |
2808 KB |
Output is correct |
14 |
Correct |
7 ms |
2680 KB |
Output is correct |
15 |
Correct |
7 ms |
2808 KB |
Output is correct |
16 |
Correct |
6 ms |
2808 KB |
Output is correct |
17 |
Correct |
7 ms |
2808 KB |
Output is correct |
18 |
Correct |
7 ms |
2808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2680 KB |
Output is correct |
2 |
Correct |
6 ms |
2680 KB |
Output is correct |
3 |
Correct |
6 ms |
2680 KB |
Output is correct |
4 |
Correct |
6 ms |
2680 KB |
Output is correct |
5 |
Correct |
6 ms |
2680 KB |
Output is correct |
6 |
Correct |
6 ms |
2680 KB |
Output is correct |
7 |
Correct |
6 ms |
2680 KB |
Output is correct |
8 |
Correct |
7 ms |
2680 KB |
Output is correct |
9 |
Correct |
6 ms |
2680 KB |
Output is correct |
10 |
Correct |
6 ms |
2680 KB |
Output is correct |
11 |
Correct |
6 ms |
2680 KB |
Output is correct |
12 |
Correct |
6 ms |
2680 KB |
Output is correct |
13 |
Correct |
7 ms |
2808 KB |
Output is correct |
14 |
Correct |
7 ms |
2680 KB |
Output is correct |
15 |
Correct |
7 ms |
2808 KB |
Output is correct |
16 |
Correct |
6 ms |
2808 KB |
Output is correct |
17 |
Correct |
7 ms |
2808 KB |
Output is correct |
18 |
Correct |
7 ms |
2808 KB |
Output is correct |
19 |
Correct |
31 ms |
3832 KB |
Output is correct |
20 |
Correct |
33 ms |
3960 KB |
Output is correct |
21 |
Correct |
46 ms |
4088 KB |
Output is correct |
22 |
Correct |
45 ms |
4344 KB |
Output is correct |
23 |
Correct |
95 ms |
9080 KB |
Output is correct |
24 |
Correct |
109 ms |
10360 KB |
Output is correct |
25 |
Correct |
131 ms |
11128 KB |
Output is correct |
26 |
Correct |
148 ms |
12280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2680 KB |
Output is correct |
2 |
Correct |
6 ms |
2680 KB |
Output is correct |
3 |
Correct |
8 ms |
2680 KB |
Output is correct |
4 |
Correct |
21 ms |
2808 KB |
Output is correct |
5 |
Correct |
79 ms |
3168 KB |
Output is correct |
6 |
Correct |
6 ms |
2680 KB |
Output is correct |
7 |
Correct |
7 ms |
2936 KB |
Output is correct |
8 |
Correct |
7 ms |
2936 KB |
Output is correct |
9 |
Correct |
9 ms |
2936 KB |
Output is correct |
10 |
Correct |
25 ms |
3064 KB |
Output is correct |
11 |
Correct |
94 ms |
3448 KB |
Output is correct |
12 |
Correct |
15 ms |
5524 KB |
Output is correct |
13 |
Correct |
16 ms |
5524 KB |
Output is correct |
14 |
Correct |
19 ms |
5672 KB |
Output is correct |
15 |
Correct |
39 ms |
5652 KB |
Output is correct |
16 |
Correct |
136 ms |
6164 KB |
Output is correct |
17 |
Correct |
317 ms |
60056 KB |
Output is correct |
18 |
Correct |
320 ms |
59928 KB |
Output is correct |
19 |
Correct |
323 ms |
60056 KB |
Output is correct |
20 |
Correct |
377 ms |
60056 KB |
Output is correct |
21 |
Correct |
676 ms |
60568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
4088 KB |
Output is correct |
2 |
Correct |
47 ms |
4088 KB |
Output is correct |
3 |
Correct |
175 ms |
4344 KB |
Output is correct |
4 |
Correct |
331 ms |
4600 KB |
Output is correct |
5 |
Correct |
127 ms |
20856 KB |
Output is correct |
6 |
Correct |
188 ms |
20984 KB |
Output is correct |
7 |
Correct |
466 ms |
21244 KB |
Output is correct |
8 |
Correct |
806 ms |
21752 KB |
Output is correct |
9 |
Correct |
736 ms |
108200 KB |
Output is correct |
10 |
Correct |
843 ms |
108328 KB |
Output is correct |
11 |
Correct |
1303 ms |
108456 KB |
Output is correct |
12 |
Correct |
1862 ms |
108968 KB |
Output is correct |
13 |
Correct |
1749 ms |
225792 KB |
Output is correct |
14 |
Correct |
1800 ms |
226140 KB |
Output is correct |
15 |
Correct |
2363 ms |
226440 KB |
Output is correct |
16 |
Correct |
3093 ms |
226440 KB |
Output is correct |
17 |
Correct |
4561 ms |
226824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5108 ms |
182920 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2680 KB |
Output is correct |
2 |
Correct |
6 ms |
2680 KB |
Output is correct |
3 |
Correct |
6 ms |
2680 KB |
Output is correct |
4 |
Correct |
6 ms |
2680 KB |
Output is correct |
5 |
Correct |
6 ms |
2680 KB |
Output is correct |
6 |
Correct |
6 ms |
2680 KB |
Output is correct |
7 |
Correct |
6 ms |
2680 KB |
Output is correct |
8 |
Correct |
7 ms |
2680 KB |
Output is correct |
9 |
Correct |
6 ms |
2680 KB |
Output is correct |
10 |
Correct |
6 ms |
2680 KB |
Output is correct |
11 |
Correct |
6 ms |
2680 KB |
Output is correct |
12 |
Correct |
6 ms |
2680 KB |
Output is correct |
13 |
Correct |
7 ms |
2808 KB |
Output is correct |
14 |
Correct |
7 ms |
2680 KB |
Output is correct |
15 |
Correct |
7 ms |
2808 KB |
Output is correct |
16 |
Correct |
6 ms |
2808 KB |
Output is correct |
17 |
Correct |
7 ms |
2808 KB |
Output is correct |
18 |
Correct |
7 ms |
2808 KB |
Output is correct |
19 |
Correct |
31 ms |
3832 KB |
Output is correct |
20 |
Correct |
33 ms |
3960 KB |
Output is correct |
21 |
Correct |
46 ms |
4088 KB |
Output is correct |
22 |
Correct |
45 ms |
4344 KB |
Output is correct |
23 |
Correct |
95 ms |
9080 KB |
Output is correct |
24 |
Correct |
109 ms |
10360 KB |
Output is correct |
25 |
Correct |
131 ms |
11128 KB |
Output is correct |
26 |
Correct |
148 ms |
12280 KB |
Output is correct |
27 |
Correct |
6 ms |
2680 KB |
Output is correct |
28 |
Correct |
6 ms |
2680 KB |
Output is correct |
29 |
Correct |
8 ms |
2680 KB |
Output is correct |
30 |
Correct |
21 ms |
2808 KB |
Output is correct |
31 |
Correct |
79 ms |
3168 KB |
Output is correct |
32 |
Correct |
6 ms |
2680 KB |
Output is correct |
33 |
Correct |
7 ms |
2936 KB |
Output is correct |
34 |
Correct |
7 ms |
2936 KB |
Output is correct |
35 |
Correct |
9 ms |
2936 KB |
Output is correct |
36 |
Correct |
25 ms |
3064 KB |
Output is correct |
37 |
Correct |
94 ms |
3448 KB |
Output is correct |
38 |
Correct |
15 ms |
5524 KB |
Output is correct |
39 |
Correct |
16 ms |
5524 KB |
Output is correct |
40 |
Correct |
19 ms |
5672 KB |
Output is correct |
41 |
Correct |
39 ms |
5652 KB |
Output is correct |
42 |
Correct |
136 ms |
6164 KB |
Output is correct |
43 |
Correct |
317 ms |
60056 KB |
Output is correct |
44 |
Correct |
320 ms |
59928 KB |
Output is correct |
45 |
Correct |
323 ms |
60056 KB |
Output is correct |
46 |
Correct |
377 ms |
60056 KB |
Output is correct |
47 |
Correct |
676 ms |
60568 KB |
Output is correct |
48 |
Correct |
19 ms |
4088 KB |
Output is correct |
49 |
Correct |
47 ms |
4088 KB |
Output is correct |
50 |
Correct |
175 ms |
4344 KB |
Output is correct |
51 |
Correct |
331 ms |
4600 KB |
Output is correct |
52 |
Correct |
127 ms |
20856 KB |
Output is correct |
53 |
Correct |
188 ms |
20984 KB |
Output is correct |
54 |
Correct |
466 ms |
21244 KB |
Output is correct |
55 |
Correct |
806 ms |
21752 KB |
Output is correct |
56 |
Correct |
736 ms |
108200 KB |
Output is correct |
57 |
Correct |
843 ms |
108328 KB |
Output is correct |
58 |
Correct |
1303 ms |
108456 KB |
Output is correct |
59 |
Correct |
1862 ms |
108968 KB |
Output is correct |
60 |
Correct |
1749 ms |
225792 KB |
Output is correct |
61 |
Correct |
1800 ms |
226140 KB |
Output is correct |
62 |
Correct |
2363 ms |
226440 KB |
Output is correct |
63 |
Correct |
3093 ms |
226440 KB |
Output is correct |
64 |
Correct |
4561 ms |
226824 KB |
Output is correct |
65 |
Execution timed out |
5108 ms |
182920 KB |
Time limit exceeded |
66 |
Halted |
0 ms |
0 KB |
- |