Submission #1226520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226520		akqxolotl	Magic Tree (CEOI19_magictree)	C++20	3 / 100	98 ms	20804 KiB

magictree

//Segment Tree is a State of Mind
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugl(x) cerr << #x << " is "; for(auto p : x) cerr << p << " "; cerr << endl;
#define debugpl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p.first<<" "<<p.second<<endl;cerr<<endl;

#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()

int inf=4e18+5;
int mod=1e9+7;

const int MAXN=1e5+5;
int pre[MAXN],pos[MAXN];
int cnt=0;
vi c[MAXN];

void dfs(int x){
	cnt++;
	pre[x]=cnt;
	for(int i:c[x])dfs(i);
	pos[x]=cnt;
}

struct node{
	
	int s,e,m,v,z;
	node *l=nullptr,*r=nullptr;
	
	node(int S,int E){
		s=S,e=E,m=(s+e)/2;
		v=0;
		z=-1;
	}
	
	void cre(){
		if(s==e)return;
		l=new node(s,m);
		r=new node(m+1,e);
	}
	
	void prop(){
		if(z==-1)return;
		v=z*(e-s+1);
		if(s!=e){
			if(l==nullptr)cre();
			l->z=z;
			r->z=z;
		}
		z=-1;
	}
	
	void ud(int S,int E,int V){
		if(s==S&&e==E){
			z=V;
			return;
		}
		if(l==nullptr)cre();
		if(E<=m)l->ud(S,E,V);
		else if(S>m)r->ud(S,E,V);
		else l->ud(S,m,V),r->ud(m+1,E,V);
		prop();
		l->prop(),r->prop();
		v=l->v+r->v;
	}
	
	int qr(int S,int E){
		prop();
		if(s==S&&e==E)return v;
		if(l==nullptr)cre();
		if(E<=m)return l->qr(S,E);
		else if(S>m)return r->qr(S,E);
		else return l->qr(S,m)+r->qr(m+1,E);
	}
}*root=new node(1,100005);

struct fruit{
	int v,d,w;
};

bool cmp(fruit a, fruit b){
	if(a.d>b.d)return 1;
	else if(a.d<b.d)return 0;
	else return pre[a.v]<pre[b.v];
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
	int n,m,k;cin>>n>>m>>k;
	fruit a[m];
	for(int i=2;i<=n;i++){
		int p;cin>>p;
		c[p].pb(i);
	}
	for(int i=0;i<m;i++)cin>>a[i].v>>a[i].d>>a[i].w;
	dfs(1);
	sort(a,a+m,cmp);
	for(int i=0;i<m;i++){
		int q=root->qr(pre[a[i].v],pos[a[i].v]);
		if(a[i].w>q){
			root->ud(pre[a[i].v],pos[a[i].v],0);
			root->ud(pre[a[i].v],pre[a[i].v],a[i].w);
		}
	}
	cout<<root->qr(1,n)<<'\n';
}

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