oj.uz

Submission #779498

# Submission time Handle Problem Language Result Execution time Memory
779498 2023-07-11T13:26:22 Z sdgdgssdg Dynamic Diameter (CEOI19_diameter) C++14
73 / 100
 5000 ms 182248 KB 
//diameter
#include <bits/stdc++.h>
#define MAX 205000
#define SMAX 5550000 
 
using ll = long long;
typedef std::pair<int,int> pii;
ll tab[SMAX*4],lazy[SMAX*4];
void propag(int pos){
	tab[pos]+=lazy[pos];
	if(pos*2<SMAX*4){
		lazy[pos*2]+=lazy[pos];
		lazy[(pos*2)+1]+=lazy[pos];
	}
	lazy[pos]=0;
}
ll query(int l,int r,int la=0,int ra=SMAX-1,int pos=1){
	propag(pos);
	if(la>r||ra<l)return 0;
	if(la>=l&&ra<=r){
		return tab[pos];
	}
	int m = (la+ra)/2;
	return std::max(query(l,r,la,m,pos*2),query(l,r,m+1,ra,(pos*2)+1));
}
void lazyadd(int l,int r,ll k,int la=0,int ra=SMAX-1,int pos=1){
	propag(pos);
	if(la>r||ra<l)return;
	if(la>=l&&ra<=r){
		lazy[pos]+=k;
		propag(pos);
		return;
	}
	int m = (la+ra)/2;
	lazyadd(l,r,k,la,m,pos*2);
	lazyadd(l,r,k,m+1,ra,(pos*2)+1);
	tab[pos]=std::max(tab[pos*2],tab[(pos*2)+1]);
}
std::vector<pii> con[MAX];
ll N,Q,W;
ll peso[MAX];
bool bloqueado[MAX];
inline int dfs(int pos,int prev){
	int s=1;
	for(auto&x:con[pos]){
		if(x.first==prev)continue;
		if(bloqueado[x.first])continue;
		s+=dfs(x.first,pos);
	}
	return s;
}
int centroide=0;
inline int find_centroide(int pos,int prev,int sz){
	int b=0;
	int c=1;
	for(auto&x:con[pos]){
		if(x.first==prev)continue;
		if(bloqueado[x.first])continue;
		int d = find_centroide(x.first,pos,sz);
		b=std::max(b,d);
		c+=d;
	}
	if(std::max(b,sz-c)<=sz/2){
		centroide=pos;
	}
	return c;
}
int cureuler=0;
pii rangeeuler[MAX][20];
pii rangeedges[MAX][20];
int ancestralmaior[MAX][20];
int centronivel[MAX][20];
int valores[SMAX];
inline void montar_euler(int pos,int prev,int lvl,int C){
	centronivel[pos][lvl]=C;
	++cureuler;
	valores[cureuler]=pos;
	rangeeuler[pos][lvl].first=cureuler;
	for(auto&x:con[pos]){
		if(x.first==prev)continue;
		if(bloqueado[x.first])continue;
		montar_euler(x.first,pos,lvl,C);
	}
	rangeeuler[pos][lvl].second=cureuler;
}
inline void setar_euler(int pos,int prev,int lvl,int paimax){
	ancestralmaior[pos][lvl]=paimax;
	for(auto&x:con[pos]){
		if(x.first==prev)continue;
		if(bloqueado[x.first])continue;
		rangeedges[x.second][lvl]=rangeeuler[x.first][lvl];
		if(prev==-1)
			setar_euler(x.first,pos,lvl,x.first);
		else
			setar_euler(x.first,pos,lvl,paimax);
	}
}
int virou_centroide[MAX];
int farthest(int la,int ra){
	ll goal=query(la,ra);
	int l=la,r=ra;
	while(l<r){
		int m = (l+r)/2;
		if(query(la,m)==goal){
			r=m;
		}else l=m+1;
	}
	return l;
}
ll pega_custo_otter(int otter,int lvl){
	int C = centronivel[otter][lvl];
	int maisdist=otter;
	if(maisdist==C)return query(rangeeuler[maisdist][lvl].first,rangeeuler[maisdist][lvl].first);
	ll pega = ancestralmaior[maisdist][lvl];
	assert(pega!=-1);
	pii ragpai = rangeeuler[C][lvl];
	ll p1 = query(rangeeuler[maisdist][lvl].first,rangeeuler[maisdist][lvl].first);
	pii ragfil = rangeeuler[pega][lvl];
	ll p2 = std::max(query(ragpai.first,ragfil.first-1),query(ragfil.second+1,ragpai.second));
	return p1+p2;
}
int raiz=0;
void decompor_centroide(int X,int lvl=0){
	int SZ = dfs(X,-1);
	find_centroide(X,-1,SZ);
	int C = centroide;
	virou_centroide[C]=lvl;
	///Do centroid stuff
	montar_euler(C,-1,lvl,C);
	setar_euler(C,-1,lvl,-1);
	bloqueado[C]=1;
	if(!lvl)raiz=C;
	for(auto&x:con[C]){
		if(!bloqueado[x.first])decompor_centroide(x.first,lvl+1);
	}
}
void altera_aresta(int X,ll novo){
	ll delta = novo-peso[X];
	for(int i=0;i!=20;++i){
		if(rangeedges[X][i].first==0)continue;
		lazyadd(rangeedges[X][i].first,rangeedges[X][i].second,delta);
	}
	peso[X]=novo;
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>N>>Q>>W;
	for(int i=0;i!=N-1;++i){
		ll a,b,c;
		std::cin>>a>>b>>c;--a;--b;
		con[a].push_back({b,i});
		con[b].push_back({a,i});
		peso[i]=c;
	}
	decompor_centroide(0);
	for(int i=0;i!=N-1;++i){
		ll kek=peso[i];
		peso[i]=0;
		altera_aresta(i,kek);
	}
	assert(cureuler<SMAX);
	ll last=0;
	for(int i=0;i!=Q;++i){
		ll a,b;
		std::cin>>a>>b;a=(a+last)%(N-1);b=(b+last)%W;
		altera_aresta(a,b);
		ll best=0;
		int maisdist = valores[farthest(rangeeuler[raiz][0].first,rangeeuler[raiz][0].second)];
		for(int i=0;i<=virou_centroide[maisdist];++i)best=std::max(best,pega_custo_otter(maisdist,i));
		last=best;
		std::cout<<last<<"\n";
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 3 ms 5332 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 3 ms 5332 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 4 ms 5460 KB Output is correct
14 Correct 3 ms 5460 KB Output is correct
15 Correct 4 ms 5368 KB Output is correct
16 Correct 4 ms 5408 KB Output is correct
17 Correct 4 ms 5412 KB Output is correct
18 Correct 4 ms 5460 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 3 ms 5332 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 3 ms 5332 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 4 ms 5460 KB Output is correct
14 Correct 3 ms 5460 KB Output is correct
15 Correct 4 ms 5368 KB Output is correct
16 Correct 4 ms 5408 KB Output is correct
17 Correct 4 ms 5412 KB Output is correct
18 Correct 4 ms 5460 KB Output is correct
19 Correct 58 ms 6420 KB Output is correct
20 Correct 63 ms 6572 KB Output is correct
21 Correct 65 ms 6564 KB Output is correct
22 Correct 70 ms 6672 KB Output is correct
23 Correct 79 ms 10660 KB Output is correct
24 Correct 95 ms 11432 KB Output is correct
25 Correct 106 ms 11856 KB Output is correct
26 Correct 132 ms 12536 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 4 ms 5284 KB Output is correct
3 Correct 8 ms 5332 KB Output is correct
4 Correct 57 ms 5500 KB Output is correct
5 Correct 280 ms 5936 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Correct 5 ms 5716 KB Output is correct
9 Correct 15 ms 5768 KB Output is correct
10 Correct 106 ms 5872 KB Output is correct
11 Correct 442 ms 6236 KB Output is correct
12 Correct 7 ms 8532 KB Output is correct
13 Correct 8 ms 8788 KB Output is correct
14 Correct 19 ms 8788 KB Output is correct
15 Correct 174 ms 8908 KB Output is correct
16 Correct 643 ms 9420 KB Output is correct
17 Correct 94 ms 65816 KB Output is correct
18 Correct 81 ms 67332 KB Output is correct
19 Correct 99 ms 70908 KB Output is correct
20 Correct 267 ms 72688 KB Output is correct
21 Correct 938 ms 71612 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6552 KB Output is correct
2 Correct 118 ms 6660 KB Output is correct
3 Correct 566 ms 6852 KB Output is correct
4 Correct 1130 ms 7196 KB Output is correct
5 Correct 62 ms 19280 KB Output is correct
6 Correct 265 ms 19268 KB Output is correct
7 Correct 909 ms 19532 KB Output is correct
8 Correct 1793 ms 19824 KB Output is correct
9 Correct 297 ms 83116 KB Output is correct
10 Correct 498 ms 83128 KB Output is correct
11 Correct 1459 ms 83388 KB Output is correct
12 Correct 2651 ms 83692 KB Output is correct
13 Correct 614 ms 168304 KB Output is correct
14 Correct 866 ms 168380 KB Output is correct
15 Correct 1905 ms 168488 KB Output is correct
16 Correct 3136 ms 168812 KB Output is correct
17 Correct 3312 ms 168784 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3337 ms 140332 KB Output is correct
2 Correct 3310 ms 143220 KB Output is correct
3 Correct 3180 ms 142348 KB Output is correct
4 Correct 2888 ms 143456 KB Output is correct
5 Correct 2589 ms 137284 KB Output is correct
6 Correct 3043 ms 106676 KB Output is correct
7 Correct 4849 ms 168636 KB Output is correct
8 Correct 4930 ms 168568 KB Output is correct
9 Correct 4728 ms 168888 KB Output is correct
10 Correct 4600 ms 168544 KB Output is correct
11 Correct 3803 ms 161868 KB Output is correct
12 Correct 4318 ms 120560 KB Output is correct
13 Correct 4994 ms 181948 KB Output is correct
14 Correct 4800 ms 182248 KB Output is correct
15 Correct 4522 ms 181248 KB Output is correct
16 Correct 3968 ms 181740 KB Output is correct
17 Correct 3964 ms 173192 KB Output is correct
18 Correct 3852 ms 124888 KB Output is correct
19 Correct 4593 ms 182200 KB Output is correct
20 Correct 4675 ms 181996 KB Output is correct
21 Correct 4820 ms 182160 KB Output is correct
22 Correct 4252 ms 181532 KB Output is correct
23 Correct 3999 ms 173044 KB Output is correct
24 Correct 3882 ms 125888 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 3 ms 5332 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 3 ms 5332 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Correct 4 ms 5460 KB Output is correct
14 Correct 3 ms 5460 KB Output is correct
15 Correct 4 ms 5368 KB Output is correct
16 Correct 4 ms 5408 KB Output is correct
17 Correct 4 ms 5412 KB Output is correct
18 Correct 4 ms 5460 KB Output is correct
19 Correct 58 ms 6420 KB Output is correct
20 Correct 63 ms 6572 KB Output is correct
21 Correct 65 ms 6564 KB Output is correct
22 Correct 70 ms 6672 KB Output is correct
23 Correct 79 ms 10660 KB Output is correct
24 Correct 95 ms 11432 KB Output is correct
25 Correct 106 ms 11856 KB Output is correct
26 Correct 132 ms 12536 KB Output is correct
27 Correct 4 ms 5332 KB Output is correct
28 Correct 4 ms 5284 KB Output is correct
29 Correct 8 ms 5332 KB Output is correct
30 Correct 57 ms 5500 KB Output is correct
31 Correct 280 ms 5936 KB Output is correct
32 Correct 3 ms 5332 KB Output is correct
33 Correct 3 ms 5716 KB Output is correct
34 Correct 5 ms 5716 KB Output is correct
35 Correct 15 ms 5768 KB Output is correct
36 Correct 106 ms 5872 KB Output is correct
37 Correct 442 ms 6236 KB Output is correct
38 Correct 7 ms 8532 KB Output is correct
39 Correct 8 ms 8788 KB Output is correct
40 Correct 19 ms 8788 KB Output is correct
41 Correct 174 ms 8908 KB Output is correct
42 Correct 643 ms 9420 KB Output is correct
43 Correct 94 ms 65816 KB Output is correct
44 Correct 81 ms 67332 KB Output is correct
45 Correct 99 ms 70908 KB Output is correct
46 Correct 267 ms 72688 KB Output is correct
47 Correct 938 ms 71612 KB Output is correct
48 Correct 16 ms 6552 KB Output is correct
49 Correct 118 ms 6660 KB Output is correct
50 Correct 566 ms 6852 KB Output is correct
51 Correct 1130 ms 7196 KB Output is correct
52 Correct 62 ms 19280 KB Output is correct
53 Correct 265 ms 19268 KB Output is correct
54 Correct 909 ms 19532 KB Output is correct
55 Correct 1793 ms 19824 KB Output is correct
56 Correct 297 ms 83116 KB Output is correct
57 Correct 498 ms 83128 KB Output is correct
58 Correct 1459 ms 83388 KB Output is correct
59 Correct 2651 ms 83692 KB Output is correct
60 Correct 614 ms 168304 KB Output is correct
61 Correct 866 ms 168380 KB Output is correct
62 Correct 1905 ms 168488 KB Output is correct
63 Correct 3136 ms 168812 KB Output is correct
64 Correct 3312 ms 168784 KB Output is correct
65 Correct 3337 ms 140332 KB Output is correct
66 Correct 3310 ms 143220 KB Output is correct
67 Correct 3180 ms 142348 KB Output is correct
68 Correct 2888 ms 143456 KB Output is correct
69 Correct 2589 ms 137284 KB Output is correct
70 Correct 3043 ms 106676 KB Output is correct
71 Correct 4849 ms 168636 KB Output is correct
72 Correct 4930 ms 168568 KB Output is correct
73 Correct 4728 ms 168888 KB Output is correct
74 Correct 4600 ms 168544 KB Output is correct
75 Correct 3803 ms 161868 KB Output is correct
76 Correct 4318 ms 120560 KB Output is correct
77 Correct 4994 ms 181948 KB Output is correct
78 Correct 4800 ms 182248 KB Output is correct
79 Correct 4522 ms 181248 KB Output is correct
80 Correct 3968 ms 181740 KB Output is correct
81 Correct 3964 ms 173192 KB Output is correct
82 Correct 3852 ms 124888 KB Output is correct
83 Correct 4593 ms 182200 KB Output is correct
84 Correct 4675 ms 181996 KB Output is correct
85 Correct 4820 ms 182160 KB Output is correct
86 Correct 4252 ms 181532 KB Output is correct
87 Correct 3999 ms 173044 KB Output is correct
88 Correct 3882 ms 125888 KB Output is correct
89 Correct 3978 ms 143444 KB Output is correct
90 Correct 4163 ms 154424 KB Output is correct
91 Correct 4525 ms 167284 KB Output is correct
92 Correct 4858 ms 170500 KB Output is correct
93 Correct 4625 ms 175288 KB Output is correct
94 Correct 4655 ms 176736 KB Output is correct
95 Correct 4900 ms 180156 KB Output is correct
96 Execution timed out 5068 ms 179916 KB Time limit exceeded
97 Halted 0 ms 0 KB -