Submission #1226531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226531		jellybean	Magic Tree (CEOI19_magictree)	C++20	20 / 100	100 ms	26780 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define dl(x) cout<<#x<<" is "<<endl; for(auto i:x) cout<<i<<' '; cout<<endl;
#define fi first
#define se second
typedef pair<int,int> pii;
typedef pair<int,pii> fruit;

const int N = 1e5+5;
vector<int>adj[N];
int st[N], en[N], par[N];

bool cmp(fruit a, fruit b){
	if(a.fi == b.fi) return st[a.se.fi] > st[b.se.fi];
	else return a.fi < b.fi;
}

int cnt = 1;
void dfs(int x, int p){
	st[x] = cnt++;
	for(auto i: adj[x]){
		if(i == p) continue;
		dfs(i,x);
	}
	en[x] = cnt-1;
}

struct node{
	int s,e,m,val=0;
	node *l=nullptr, *r=nullptr;
	
	node(int S, int E){
		s=S,e=E,m=(s+e)/2;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void upd(int x, int v){
		if(s==e) val = v;
		else{
			if(x<=m) l->upd(x,v);
			else r->upd(x,v);
			val = max(l->val,r->val);
		}
	}
	
	int query(int S, int E){
		if(s==S and e==E) return val;
		if(E<=m) return l->query(S,E);
		if(S>m) return r->query(S,E);
		return max(l->query(S,m),r->query(m+1,E));
	}
}*root;

int ans(int x, int p, int f){
	if(f == 1) return root->query(st[x],st[x]);
	
	int res = 0;
	for(auto i:adj[x]){
		if(i == p) continue;
		res += max(ans(i,x,1), ans(i,x,0));
	}
	return res;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n,m,k; cin>>n>>m>>k;
	for(int i=2; i<=n; i++){
		int j; cin>>j;
		adj[i].pb(j);
		adj[j].pb(i);
		par[i] = j;
	}
	
	dfs(1,-1);
	
	fruit fruits[m];
	for(int i=0; i<m; i++){
		int v,d,w; cin>>v>>d>>w;
		fruits[i] = {d,{v,w}};
	}
	
	sort(fruits, fruits+m, cmp);
	//dd(1)
	//for(auto[d,p]:fruits) cout<<d<<" "<<p.fi<<' '<<p.se<<endl;
	
	root = new node(1,n);
	
	int ptr = 0;
	for(int day=1; day<=k; day++){
		while(ptr != n and fruits[ptr].fi == day){
			//dd(day)
			auto[d,p] = fruits[ptr];
			auto[u,w] = p;
			
			int sum = 0;
			for(auto v: adj[u]){
				if(v == par[u]) continue;
				sum += root->query(st[v],en[v]);
			}
			
			root->upd(st[u],sum+w);
			//dd2(st[u],sum+w)
			
			ptr++;
		}
	}
	
	cout<<ans(1,-1,0);
	
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17