oj.uz

Submission #1095793

# Submission time Handle Problem Language Result Execution time Memory
1095793 2024-10-03T07:36:00 Z alexander707070 Magic Tree (CEOI19_magictree) C++14
45 / 100
 2000 ms 23088 KB 
#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

int n,m,k,p[MAXN],a,d,w,sz[MAXN],heavy[MAXN];
pair<int,int> cost[MAXN];
vector<int> v[MAXN];

struct event{
	int l,r;
	long long val;
};

struct ST{
	struct node{
		long long mins,maxs;
		long long setv,addv;

		inline friend node operator + (node fr,node sc){
			return {min(fr.mins,sc.mins),max(fr.maxs,sc.maxs),-1,0};
		}
	};

	node tree[4*MAXN];
	vector<event> w;

	void combine(node &v,long long s,bool type){
		if(!type){
			v.mins+=s; v.maxs+=s; v.addv+=s;
		}else{
			v.mins=v.maxs=s; v.setv=s; v.addv=0;
		}
	}

	void psh(int v){
		if(tree[v].setv!=-1){
			combine(tree[2*v],tree[v].setv,true);
			combine(tree[2*v+1],tree[v].setv,true);

			tree[v].setv=-1;
		}

		if(tree[v].addv!=0){
			combine(tree[2*v],tree[v].addv,false);
			combine(tree[2*v+1],tree[v].addv,false);

			tree[v].addv=0;
		}
	}

	void update(int v,int l,int r,int ll,int rr,long long s,bool type){
		if(ll>rr)return;
		if(l==ll and r==rr){
			combine(tree[v],s,type);
		}else{
			psh(v);
			int tt=(l+r)/2;
			update(2*v,l,tt,ll,min(tt,r),s,type);
			update(2*v+1,tt+1,r,max(tt+1,ll),rr,s,type);

			tree[v]=tree[2*v]+tree[2*v+1];
		}
	}

	long long getval(int v,int l,int r,int pos){
		if(l==r)return tree[v].mins;

		psh(v);
		int tt=(l+r)/2;
		if(pos<=tt)return getval(2*v,l,tt,pos);
		else return getval(2*v+1,tt+1,r,pos);
	}

	void dfs(int v,int l,int r){
		if(tree[v].mins==tree[v].maxs){
			if(w.empty() or w.back().val!=tree[v].mins){
				w.push_back({l,r,tree[v].mins});
			}else w.back().r=r;
		}else{
			int tt=(l+r)/2;
			psh(v);
			dfs(2*v,l,tt);
			dfs(2*v+1,tt+1,r);
		}
	}

	void init(){
		w.clear();
		update(1,1,k,1,k,0,true);
	}
};

struct bruh{
	long long dp[MAXN];

	void update(int l,int r,long long s,bool type){
		for(int i=l;i<=r;i++){
			if(!type)dp[i]+=s;
			else dp[i]=s;
		}
	}

	long long getval(int pos){
		return dp[pos];
	}

	vector<event> w;

	void dfs(){
		int last=1;
		for(int i=1;i<=k;i++){
			if(i==k or dp[i]!=dp[i+1]){
				w.push_back({last,i,dp[i]});
				last=i+1;
			}
		}
	}

	void init(){
		w.clear();
		update(1,k,0,true);
	}
}seg;

void dfs(int x){
	sz[x]=1;

	for(int i=0;i<v[x].size();i++){
		dfs(v[x][i]);
		sz[x]+=sz[v[x][i]];
		if(sz[v[x][i]]>sz[heavy[x]])heavy[x]=v[x][i];
	}
}

void solve(int x){

	vector<event> s;
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==heavy[x])continue;
		solve(v[x][i]);

		seg.dfs();
		for(event curr:seg.w){
			s.push_back(curr);
		}

		seg.init();
	}

	if(heavy[x]!=0){
		solve(heavy[x]);
	}

	for(event curr:s){
		seg.update(curr.l,curr.r,curr.val,false);
	}

	if(cost[x].first==0)return;

	long long newval=seg.getval(cost[x].first)+cost[x].second;
	int l=cost[x].first,r=k+1,tt;

	while(l+1<r){
		tt=(l+r)/2;
		if(seg.getval(tt)<newval){
			l=tt;
		}else{
			r=tt;
		}
	}

	seg.update(cost[x].first,l,newval,true);
	return;
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>m>>k;
	for(int i=2;i<=n;i++){
		cin>>p[i];
		v[p[i]].push_back(i);
	}

	dfs(1);

	for(int i=1;i<=m;i++){
		cin>>a>>d>>w;
		cost[a]={d,w};
	}

	solve(1);
	cout<<seg.dp[k]<<"\n";

    return 0;
}

Compilation message

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:128:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
magictree.cpp: In function 'void solve(int)':
magictree.cpp:138:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 7760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 42 ms 23088 KB Output is correct
5 Correct 1889 ms 23028 KB Output is correct
6 Correct 60 ms 22924 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7504 KB Output is correct
2 Correct 33 ms 7508 KB Output is correct
3 Correct 39 ms 13656 KB Output is correct
4 Correct 25 ms 9804 KB Output is correct
5 Correct 35 ms 21588 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2820 KB Output is correct
10 Correct 44 ms 7628 KB Output is correct
11 Correct 35 ms 7768 KB Output is correct
12 Correct 31 ms 14108 KB Output is correct
13 Correct 32 ms 10064 KB Output is correct
14 Correct 42 ms 21844 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1178 ms 3932 KB Output is correct
2 Execution timed out 2059 ms 7260 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2820 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 2 ms 2908 KB Output is correct
12 Correct 1 ms 2908 KB Output is correct
13 Correct 42 ms 23088 KB Output is correct
14 Correct 1889 ms 23028 KB Output is correct
15 Correct 60 ms 22924 KB Output is correct
16 Correct 44 ms 7628 KB Output is correct
17 Correct 35 ms 7768 KB Output is correct
18 Correct 31 ms 14108 KB Output is correct
19 Correct 32 ms 10064 KB Output is correct
20 Correct 42 ms 21844 KB Output is correct
21 Correct 48 ms 3996 KB Output is correct
22 Correct 239 ms 7764 KB Output is correct
23 Execution timed out 2069 ms 8568 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2820 KB Output is correct
10 Execution timed out 2069 ms 7760 KB Time limit exceeded
11 Halted 0 ms 0 KB -