Submission #1110854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110854		_rain_	Magic Tree (CEOI19_magictree)	C++14	3 / 100	89 ms	17480 KiB

magictree

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
#define name "main"
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)

const int N=1'00'000;
vector<int>ke[N+2];
void add_edge(int u,int v){
	ke[u].push_back(v),ke[v].push_back(u);
	return;
}
int p[N+2],goc[N+2],d[N+2],w[N+2];
int timedfs=0,sta[N+2],fin[N+2],id[N+2];
LL val[N+2],dp[N+2];
int n,m,k;

void dfs(int u,int p){
	sta[u]=++timedfs;
	for(auto&v:ke[u]){
		if (v==p) continue;
		dfs(v,u);
	}
	fin[u]=timedfs;
}
LL st[N*4+2];
#define lef(id) id<<1
#define rig(id) id<<1|1
void upd(int id,int l,int r,int p,LL val){
	if (l>p||r<p) return;
	if (l==r){
		st[id]+=val;
	}
	else{
		int m=(l+r)>>1;
		upd(lef(id),l,m,p,val);
		upd(rig(id),m+1,r,p,val);
		st[id]=st[lef(id)]+st[rig(id)];
	}
}

LL Get(int id,int l,int r,int u,int v){
	if (l>v||r<u) return 0;
	if (u<=l&&r<=v) return st[id];
	int m=(l+r)>>1;
	return Get(lef(id),l,m,u,v)+Get(rig(id),m+1,r,u,v);
}
void dfsdp(int u,int p){
	LL sum=0;
	for(auto&v:ke[u]){
		if(v==p) continue;
		dfsdp(v,u),sum+=dp[v];
	}
	dp[u]=max(val[u],sum);
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	scanf("%d%d%d",&n,&m,&k);
	iota(id,id+n+1,0);
	FOR(i,2,n){
		scanf("%d",&p[i]);
		add_edge(i,p[i]);
	}
	FOR(i,1,m){
		int r,ng,gt;scanf("%d%d%d",&r,&ng,&gt);
		d[r]=ng,w[r]=gt;
	}
	dfs(1,0);
	sort(id+1,id+n+1,
		[=](int x,int y){
			return d[x]<d[y];
		});
	FOR(i,1,n){
		upd(1,1,n,sta[id[i]],w[id[i]]);
		val[id[i]]=Get(1,1,n,sta[id[i]],fin[id[i]]);
	}
	dfsdp(1,0);
	printf("%lld",dp[1]);
	exit(0);
}

Compilation message (stderr)

magictree.cpp: In function 'int32_t main()':
magictree.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d%d%d",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
magictree.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d",&p[i]);
      |   ~~~~~^~~~~~~~~~~~
magictree.cpp:69:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   int r,ng,gt;scanf("%d%d%d",&r,&ng,&gt);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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