oj.uz

Submission #227573

# Submission time Handle Problem Language Result Execution time Memory
227573 2020-04-27T21:24:33 Z alishahali1382 Dynamic Diameter (CEOI19_diameter) C++14
100 / 100
 541 ms 63804 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 100010, LOG=20;

struct Node{
	ll a, b, c, ab, bc, abc=0;
	Node(ll x=0) : a(x), b(-2*x), c(x), ab(-x), bc(-x){}
};

Node operator +(Node x, Node y){
	Node out;
	out.a=max(x.a, y.a);
	out.b=max(x.b, y.b);
	out.c=max(x.c, y.c);
	out.ab=max(max(x.ab, y.ab), x.a+y.b);
	out.bc=max(max(x.bc, y.bc), x.b+y.c);
	out.abc=max(max(x.abc, y.abc), max(x.ab+y.c, x.a+y.bc));
	return out;	
}

ll n, m, w, u, v, x, y, t, a, b, last;
ll W[MAXN];
int E[MAXN][2];
int id[MAXN];
int stt[MAXN], fnt[MAXN], timer=1;
Node seg[MAXN<<3];
ll lazy[MAXN<<3];
vector<pii> G[MAXN];

void add_lazy(int id, ll val){
	seg[id].a+=val;
	seg[id].b-=2*val;
	seg[id].c+=val;
	seg[id].ab-=val;
	seg[id].bc-=val;
	lazy[id]+=val;
}

void shift(int id){
	if (!lazy[id]) return ;
	add_lazy(id<<1, lazy[id]);
	add_lazy(id<<1 | 1, lazy[id]);
	lazy[id]=0;
}

void Add(int id, int tl, int tr, int l, int r, ll val){
	//if (id==1) cerr<<"Add "<<l<<' '<<r<<"  "<<val<<'\n';
	if (r<=tl || tr<=l) return ;
	if (l<=tl && tr<=r){
		add_lazy(id, val);
		return ;
	}
	shift(id);
	int mid=(tl+tr)>>1;
	Add(id<<1, tl, mid, l, r, val);
	Add(id<<1 | 1, mid, tr, l, r, val);
	seg[id]=seg[id<<1] + seg[id<<1 | 1];
}

void dfs(int node, int par){
	stt[node]=timer++;
	for (pii p:G[node]) if (p.first!=par){
		dfs(p.first, node);
		Add(1, 1, 2*n, stt[p.first], fnt[p.first], W[p.second]);
		id[p.first]=p.second;
	}
	fnt[node]=timer++;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>w;
	for (int i=0; i<n-1; i++){
		cin>>E[i][0]>>E[i][1]>>W[i];
		G[E[i][0]].pb({E[i][1], i});
		G[E[i][1]].pb({E[i][0], i});
	}
	dfs(1, 1);
	for (int i=0; i<n-1; i++) if (stt[E[i][1]]<stt[E[i][0]]) swap(E[i][0], E[i][1]);
	
	while (m--){
		cin>>x>>y;
		x=(x+last)%(n-1);
		y=(y+last)%w;
		Add(1, 1, 2*n, stt[E[x][1]], fnt[E[x][1]], y-W[x]);
		W[x]=y;
		cout<<(last=seg[1].abc)<<'\n';
	}
	
	return 0;
}
/*
4 3 2000
1 2 100
2 3 1000
2 4 1000
2 1030
1 1020
1 890


4 3 2000
1 2 100
2 3 1030
2 4 1000
2 1030
1 1020
1 890


*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 40320 KB Output is correct
2 Correct 24 ms 40320 KB Output is correct
3 Correct 23 ms 40320 KB Output is correct
4 Correct 29 ms 40192 KB Output is correct
5 Correct 25 ms 40184 KB Output is correct
6 Correct 27 ms 40320 KB Output is correct
7 Correct 25 ms 40320 KB Output is correct
8 Correct 24 ms 40284 KB Output is correct
9 Correct 25 ms 40320 KB Output is correct
10 Correct 28 ms 40320 KB Output is correct
11 Correct 28 ms 40320 KB Output is correct
12 Correct 27 ms 40320 KB Output is correct
13 Correct 28 ms 40192 KB Output is correct
14 Correct 24 ms 40320 KB Output is correct
15 Correct 24 ms 40296 KB Output is correct
16 Correct 26 ms 40320 KB Output is correct
17 Correct 27 ms 40320 KB Output is correct
18 Correct 26 ms 40320 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 40320 KB Output is correct
2 Correct 24 ms 40320 KB Output is correct
3 Correct 23 ms 40320 KB Output is correct
4 Correct 29 ms 40192 KB Output is correct
5 Correct 25 ms 40184 KB Output is correct
6 Correct 27 ms 40320 KB Output is correct
7 Correct 25 ms 40320 KB Output is correct
8 Correct 24 ms 40284 KB Output is correct
9 Correct 25 ms 40320 KB Output is correct
10 Correct 28 ms 40320 KB Output is correct
11 Correct 28 ms 40320 KB Output is correct
12 Correct 27 ms 40320 KB Output is correct
13 Correct 28 ms 40192 KB Output is correct
14 Correct 24 ms 40320 KB Output is correct
15 Correct 24 ms 40296 KB Output is correct
16 Correct 26 ms 40320 KB Output is correct
17 Correct 27 ms 40320 KB Output is correct
18 Correct 26 ms 40320 KB Output is correct
19 Correct 28 ms 40440 KB Output is correct
20 Correct 29 ms 40576 KB Output is correct
21 Correct 30 ms 40568 KB Output is correct
22 Correct 33 ms 40576 KB Output is correct
23 Correct 33 ms 41088 KB Output is correct
24 Correct 35 ms 41088 KB Output is correct
25 Correct 39 ms 41080 KB Output is correct
26 Correct 38 ms 41464 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 40312 KB Output is correct
2 Correct 23 ms 40320 KB Output is correct
3 Correct 25 ms 40320 KB Output is correct
4 Correct 32 ms 40568 KB Output is correct
5 Correct 67 ms 41464 KB Output is correct
6 Correct 24 ms 40320 KB Output is correct
7 Correct 24 ms 40320 KB Output is correct
8 Correct 25 ms 40320 KB Output is correct
9 Correct 26 ms 40440 KB Output is correct
10 Correct 35 ms 40576 KB Output is correct
11 Correct 92 ms 41720 KB Output is correct
12 Correct 30 ms 40960 KB Output is correct
13 Correct 32 ms 41008 KB Output is correct
14 Correct 33 ms 40960 KB Output is correct
15 Correct 42 ms 41216 KB Output is correct
16 Correct 106 ms 42360 KB Output is correct
17 Correct 118 ms 51180 KB Output is correct
18 Correct 115 ms 51248 KB Output is correct
19 Correct 118 ms 51304 KB Output is correct
20 Correct 138 ms 51692 KB Output is correct
21 Correct 256 ms 53048 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 40448 KB Output is correct
2 Correct 36 ms 40576 KB Output is correct
3 Correct 70 ms 41080 KB Output is correct
4 Correct 109 ms 41848 KB Output is correct
5 Correct 36 ms 41728 KB Output is correct
6 Correct 48 ms 41848 KB Output is correct
7 Correct 95 ms 42488 KB Output is correct
8 Correct 144 ms 43256 KB Output is correct
9 Correct 78 ms 46460 KB Output is correct
10 Correct 93 ms 46584 KB Output is correct
11 Correct 145 ms 47224 KB Output is correct
12 Correct 237 ms 48120 KB Output is correct
13 Correct 140 ms 52684 KB Output is correct
14 Correct 152 ms 52728 KB Output is correct
15 Correct 222 ms 53500 KB Output is correct
16 Correct 298 ms 54340 KB Output is correct
17 Correct 304 ms 54008 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 56440 KB Output is correct
2 Correct 346 ms 56440 KB Output is correct
3 Correct 346 ms 56696 KB Output is correct
4 Correct 331 ms 56444 KB Output is correct
5 Correct 411 ms 56440 KB Output is correct
6 Correct 316 ms 56176 KB Output is correct
7 Correct 411 ms 59488 KB Output is correct
8 Correct 389 ms 59384 KB Output is correct
9 Correct 384 ms 59300 KB Output is correct
10 Correct 400 ms 59384 KB Output is correct
11 Correct 448 ms 59256 KB Output is correct
12 Correct 384 ms 58328 KB Output is correct
13 Correct 463 ms 63608 KB Output is correct
14 Correct 460 ms 63764 KB Output is correct
15 Correct 477 ms 63736 KB Output is correct
16 Correct 503 ms 63608 KB Output is correct
17 Correct 442 ms 63096 KB Output is correct
18 Correct 431 ms 59760 KB Output is correct
19 Correct 493 ms 63608 KB Output is correct
20 Correct 454 ms 63736 KB Output is correct
21 Correct 517 ms 63736 KB Output is correct
22 Correct 528 ms 63804 KB Output is correct
23 Correct 436 ms 63040 KB Output is correct
24 Correct 422 ms 59888 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 40320 KB Output is correct
2 Correct 24 ms 40320 KB Output is correct
3 Correct 23 ms 40320 KB Output is correct
4 Correct 29 ms 40192 KB Output is correct
5 Correct 25 ms 40184 KB Output is correct
6 Correct 27 ms 40320 KB Output is correct
7 Correct 25 ms 40320 KB Output is correct
8 Correct 24 ms 40284 KB Output is correct
9 Correct 25 ms 40320 KB Output is correct
10 Correct 28 ms 40320 KB Output is correct
11 Correct 28 ms 40320 KB Output is correct
12 Correct 27 ms 40320 KB Output is correct
13 Correct 28 ms 40192 KB Output is correct
14 Correct 24 ms 40320 KB Output is correct
15 Correct 24 ms 40296 KB Output is correct
16 Correct 26 ms 40320 KB Output is correct
17 Correct 27 ms 40320 KB Output is correct
18 Correct 26 ms 40320 KB Output is correct
19 Correct 28 ms 40440 KB Output is correct
20 Correct 29 ms 40576 KB Output is correct
21 Correct 30 ms 40568 KB Output is correct
22 Correct 33 ms 40576 KB Output is correct
23 Correct 33 ms 41088 KB Output is correct
24 Correct 35 ms 41088 KB Output is correct
25 Correct 39 ms 41080 KB Output is correct
26 Correct 38 ms 41464 KB Output is correct
27 Correct 23 ms 40312 KB Output is correct
28 Correct 23 ms 40320 KB Output is correct
29 Correct 25 ms 40320 KB Output is correct
30 Correct 32 ms 40568 KB Output is correct
31 Correct 67 ms 41464 KB Output is correct
32 Correct 24 ms 40320 KB Output is correct
33 Correct 24 ms 40320 KB Output is correct
34 Correct 25 ms 40320 KB Output is correct
35 Correct 26 ms 40440 KB Output is correct
36 Correct 35 ms 40576 KB Output is correct
37 Correct 92 ms 41720 KB Output is correct
38 Correct 30 ms 40960 KB Output is correct
39 Correct 32 ms 41008 KB Output is correct
40 Correct 33 ms 40960 KB Output is correct
41 Correct 42 ms 41216 KB Output is correct
42 Correct 106 ms 42360 KB Output is correct
43 Correct 118 ms 51180 KB Output is correct
44 Correct 115 ms 51248 KB Output is correct
45 Correct 118 ms 51304 KB Output is correct
46 Correct 138 ms 51692 KB Output is correct
47 Correct 256 ms 53048 KB Output is correct
48 Correct 26 ms 40448 KB Output is correct
49 Correct 36 ms 40576 KB Output is correct
50 Correct 70 ms 41080 KB Output is correct
51 Correct 109 ms 41848 KB Output is correct
52 Correct 36 ms 41728 KB Output is correct
53 Correct 48 ms 41848 KB Output is correct
54 Correct 95 ms 42488 KB Output is correct
55 Correct 144 ms 43256 KB Output is correct
56 Correct 78 ms 46460 KB Output is correct
57 Correct 93 ms 46584 KB Output is correct
58 Correct 145 ms 47224 KB Output is correct
59 Correct 237 ms 48120 KB Output is correct
60 Correct 140 ms 52684 KB Output is correct
61 Correct 152 ms 52728 KB Output is correct
62 Correct 222 ms 53500 KB Output is correct
63 Correct 298 ms 54340 KB Output is correct
64 Correct 304 ms 54008 KB Output is correct
65 Correct 423 ms 56440 KB Output is correct
66 Correct 346 ms 56440 KB Output is correct
67 Correct 346 ms 56696 KB Output is correct
68 Correct 331 ms 56444 KB Output is correct
69 Correct 411 ms 56440 KB Output is correct
70 Correct 316 ms 56176 KB Output is correct
71 Correct 411 ms 59488 KB Output is correct
72 Correct 389 ms 59384 KB Output is correct
73 Correct 384 ms 59300 KB Output is correct
74 Correct 400 ms 59384 KB Output is correct
75 Correct 448 ms 59256 KB Output is correct
76 Correct 384 ms 58328 KB Output is correct
77 Correct 463 ms 63608 KB Output is correct
78 Correct 460 ms 63764 KB Output is correct
79 Correct 477 ms 63736 KB Output is correct
80 Correct 503 ms 63608 KB Output is correct
81 Correct 442 ms 63096 KB Output is correct
82 Correct 431 ms 59760 KB Output is correct
83 Correct 493 ms 63608 KB Output is correct
84 Correct 454 ms 63736 KB Output is correct
85 Correct 517 ms 63736 KB Output is correct
86 Correct 528 ms 63804 KB Output is correct
87 Correct 436 ms 63040 KB Output is correct
88 Correct 422 ms 59888 KB Output is correct
89 Correct 329 ms 55476 KB Output is correct
90 Correct 360 ms 55980 KB Output is correct
91 Correct 416 ms 57464 KB Output is correct
92 Correct 452 ms 57336 KB Output is correct
93 Correct 437 ms 60028 KB Output is correct
94 Correct 419 ms 58744 KB Output is correct
95 Correct 541 ms 60664 KB Output is correct
96 Correct 520 ms 59388 KB Output is correct
97 Correct 463 ms 60576 KB Output is correct
98 Correct 459 ms 62728 KB Output is correct
99 Correct 534 ms 60284 KB Output is correct
100 Correct 446 ms 60232 KB Output is correct