oj.uz

Submission #781238

# Submission time Handle Problem Language Result Execution time Memory
781238 2023-07-13T00:27:27 Z Deepesson Magic Tree (CEOI19_magictree) C++17
100 / 100
 950 ms 388288 KB 
#include <bits/stdc++.h>
#define MAX 105000
std::vector<int> con[MAX];
typedef std::pair<int,int> pii;
using ll = long long;
std::vector<pii> frutas[MAX];
int N,M,K;
typedef std::pair<int,ll> pil;
typedef std::pair<pil,int> ppi;
const int nodes = 2e7;
int left[nodes],right[nodes];
ll max[nodes],lazy[nodes];
int cur=3;
int aloca(){return cur++;}
class SparseTree {
	public:
	int inicio;
	int size;
	void iniciar(){
		inicio=aloca();
		size=0;
	}
	void propag(int pos){
		max[pos]+=lazy[pos];
		if(!left[pos])left[pos]=aloca();
		lazy[left[pos]]+=lazy[pos];
		if(!right[pos])right[pos]=aloca();
		lazy[right[pos]]+=lazy[pos];
		lazy[pos]=0;
	}
	ll query(int l,int r,int pos,int la=0,int ra=MAX-1){
		propag(pos);
		assert(pos);
		if(la>r||ra<l)return 0;
		if(la>=l&&ra<=r){
			return max[pos];
		}
		int m = (la+ra)/2;
		return std::max(query(l,r,left[pos],la,m),query(l,r,right[pos],m+1,ra));
	}
	void add(int l,int r,ll k,int pos,int la=0,int ra=MAX-1){
	//	std::cout<<"Envia "<<k<<"\n";
		propag(pos);
		assert(pos);
		if(la>r||ra<l)return;
		if(la>=l&&ra<=r){
			lazy[pos]+=k;
			propag(pos);
		//	std::cout<<"Somou "<<k<<"\n";
			return;
		}
		int m = (la+ra)/2;
		add(l,r,k,left[pos],la,m);
		add(l,r,k,right[pos],m+1,ra);
		max[pos]=std::max(max[left[pos]],max[right[pos]]);
		//std::cout<<"Val:"<<max[pos]<<" "<<k<<"\n";
	}
	void add(int l,int r,ll k){
		add(l,r,k,inicio);
	}
	ll query(int l,int r){
		return query(l,r,inicio);
	}
};
std::map<int,bool> acumulados[MAX];
SparseTree dfs(int pos){
	SparseTree st;
	st.iniciar();
	st.size=1;
	for(auto&x:con[pos]){
		SparseTree res = dfs(x);
		///Garante que st eh maior
		if(res.size>st.size){std::swap(res,st);acumulados[pos].swap(acumulados[x]);}
		st.size+=res.size;
		std::vector<int> vals;
		for(auto&y:acumulados[x]){
			vals.push_back(y.first);
			acumulados[pos][y.first]=1;
		}
		std::sort(vals.begin(),vals.end());
		{
			std::vector<int> garante;
			ll best=0;
			for(auto&x:vals){
				ll as = res.query(x,x);
				if(as>best){
					best=as;
					garante.push_back(x);
				}
			}
			vals=garante;
		}
		std::reverse(vals.begin(),vals.end());
		int last = MAX-50;
		for(auto&y:vals){
			ll val = res.query(y,y);
			ll left = st.query(0,y);
		//	std::cout<<"Insere "<<left<<" "<<y<<"\n";
			///right
			st.add(y,last,val);
			ll pos = st.query(y,y);
			val+=left;
			if(pos<val){
				ll delta = val-pos;
				st.add(y,y,delta);
			}
			last=y-1;
		}
	}
	assert(frutas[pos].size()<=1);
	for(auto&x:frutas[pos]){
		int dia = x.first;
		ll left = st.query(0,dia);
		ll value = x.second+left;
		ll prev = st.query(dia,dia);
		
	//	std::cout<<"add "<<dia<<" "<<left<<" "<<value<<" "<<prev<<"\n";
		if(prev<value){
			ll delta = value-prev;
			st.add(dia,dia,delta);
		}
		acumulados[pos][dia]=1;
		++st.size;
	}
//	std::cout<<"Respostas "<<pos<<"\n";
//	for(int i=0;i!=K;++i){
	//	std::cout<<st.query(i,i)<<"\n";
//	}
	return st;
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>N>>M>>K;
	for(int i=1;i!=N;++i){
		int a;
		std::cin>>a;--a;
		con[a].push_back(i);
	}
	for(int i=0;i!=M;++i){
		int v,d,w;
		std::cin>>v>>d>>w;--v;
		std::sort(frutas[v].begin(),frutas[v].end());
		frutas[v].push_back({d,w});
	}
	auto ans = dfs(0);
	std::cout<<ans.query(0,K+5)<<"\n";
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10196 KB Output is correct
2 Correct 5 ms 10196 KB Output is correct
3 Correct 5 ms 10196 KB Output is correct
4 Correct 6 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10196 KB Output is correct
7 Correct 5 ms 10196 KB Output is correct
8 Correct 5 ms 10192 KB Output is correct
9 Correct 5 ms 10196 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 151572 KB Output is correct
2 Correct 138 ms 69844 KB Output is correct
3 Correct 950 ms 388288 KB Output is correct
4 Correct 424 ms 179284 KB Output is correct
5 Correct 484 ms 182648 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 6 ms 10584 KB Output is correct
3 Correct 6 ms 10588 KB Output is correct
4 Correct 126 ms 59796 KB Output is correct
5 Correct 132 ms 59776 KB Output is correct
6 Correct 171 ms 59900 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 117312 KB Output is correct
2 Correct 262 ms 114736 KB Output is correct
3 Correct 153 ms 60448 KB Output is correct
4 Correct 269 ms 169712 KB Output is correct
5 Correct 117 ms 47956 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10196 KB Output is correct
2 Correct 5 ms 10196 KB Output is correct
3 Correct 5 ms 10196 KB Output is correct
4 Correct 6 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10196 KB Output is correct
7 Correct 5 ms 10196 KB Output is correct
8 Correct 5 ms 10192 KB Output is correct
9 Correct 5 ms 10196 KB Output is correct
10 Correct 321 ms 130864 KB Output is correct
11 Correct 298 ms 124188 KB Output is correct
12 Correct 162 ms 59388 KB Output is correct
13 Correct 269 ms 167272 KB Output is correct
14 Correct 92 ms 47328 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15956 KB Output is correct
2 Correct 41 ms 20768 KB Output is correct
3 Correct 36 ms 20572 KB Output is correct
4 Correct 42 ms 22100 KB Output is correct
5 Correct 16 ms 15552 KB Output is correct
6 Correct 34 ms 21532 KB Output is correct
7 Correct 34 ms 26944 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10196 KB Output is correct
2 Correct 5 ms 10196 KB Output is correct
3 Correct 5 ms 10196 KB Output is correct
4 Correct 6 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10196 KB Output is correct
7 Correct 5 ms 10196 KB Output is correct
8 Correct 5 ms 10192 KB Output is correct
9 Correct 5 ms 10196 KB Output is correct
10 Correct 5 ms 10580 KB Output is correct
11 Correct 6 ms 10584 KB Output is correct
12 Correct 6 ms 10588 KB Output is correct
13 Correct 126 ms 59796 KB Output is correct
14 Correct 132 ms 59776 KB Output is correct
15 Correct 171 ms 59900 KB Output is correct
16 Correct 321 ms 130864 KB Output is correct
17 Correct 298 ms 124188 KB Output is correct
18 Correct 162 ms 59388 KB Output is correct
19 Correct 269 ms 167272 KB Output is correct
20 Correct 92 ms 47328 KB Output is correct
21 Correct 121 ms 53944 KB Output is correct
22 Correct 345 ms 145780 KB Output is correct
23 Correct 468 ms 228664 KB Output is correct
24 Correct 788 ms 384476 KB Output is correct
25 Correct 431 ms 178616 KB Output is correct
26 Correct 382 ms 133792 KB Output is correct
27 Correct 283 ms 79184 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10196 KB Output is correct
2 Correct 5 ms 10196 KB Output is correct
3 Correct 5 ms 10196 KB Output is correct
4 Correct 6 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10196 KB Output is correct
7 Correct 5 ms 10196 KB Output is correct
8 Correct 5 ms 10192 KB Output is correct
9 Correct 5 ms 10196 KB Output is correct
10 Correct 331 ms 151572 KB Output is correct
11 Correct 138 ms 69844 KB Output is correct
12 Correct 950 ms 388288 KB Output is correct
13 Correct 424 ms 179284 KB Output is correct
14 Correct 484 ms 182648 KB Output is correct
15 Correct 5 ms 10580 KB Output is correct
16 Correct 6 ms 10584 KB Output is correct
17 Correct 6 ms 10588 KB Output is correct
18 Correct 126 ms 59796 KB Output is correct
19 Correct 132 ms 59776 KB Output is correct
20 Correct 171 ms 59900 KB Output is correct
21 Correct 255 ms 117312 KB Output is correct
22 Correct 262 ms 114736 KB Output is correct
23 Correct 153 ms 60448 KB Output is correct
24 Correct 269 ms 169712 KB Output is correct
25 Correct 117 ms 47956 KB Output is correct
26 Correct 321 ms 130864 KB Output is correct
27 Correct 298 ms 124188 KB Output is correct
28 Correct 162 ms 59388 KB Output is correct
29 Correct 269 ms 167272 KB Output is correct
30 Correct 92 ms 47328 KB Output is correct
31 Correct 21 ms 15956 KB Output is correct
32 Correct 41 ms 20768 KB Output is correct
33 Correct 36 ms 20572 KB Output is correct
34 Correct 42 ms 22100 KB Output is correct
35 Correct 16 ms 15552 KB Output is correct
36 Correct 34 ms 21532 KB Output is correct
37 Correct 34 ms 26944 KB Output is correct
38 Correct 121 ms 53944 KB Output is correct
39 Correct 345 ms 145780 KB Output is correct
40 Correct 468 ms 228664 KB Output is correct
41 Correct 788 ms 384476 KB Output is correct
42 Correct 431 ms 178616 KB Output is correct
43 Correct 382 ms 133792 KB Output is correct
44 Correct 283 ms 79184 KB Output is correct
45 Correct 114 ms 53892 KB Output is correct
46 Correct 391 ms 146424 KB Output is correct
47 Correct 480 ms 229148 KB Output is correct
48 Correct 829 ms 385332 KB Output is correct
49 Correct 458 ms 179316 KB Output is correct
50 Correct 459 ms 134488 KB Output is correct
51 Correct 288 ms 80008 KB Output is correct