oj.uz

Submission #1110854

# Submission time Handle Problem Language Result Execution time Memory
1110854 2024-11-10T16:00:58 Z _rain_ Magic Tree (CEOI19_magictree) C++14
3 / 100
 89 ms 17480 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8016 KB Output is correct
2 Correct 2 ms 8016 KB Output is correct
3 Incorrect 2 ms 8016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14428 KB Output is correct
2 Correct 50 ms 17480 KB Output is correct
3 Correct 76 ms 16200 KB Output is correct
4 Correct 66 ms 15808 KB Output is correct
5 Correct 89 ms 17088 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8016 KB Output is correct
2 Incorrect 3 ms 8272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 15432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8016 KB Output is correct
2 Correct 2 ms 8016 KB Output is correct
3 Incorrect 2 ms 8016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 10840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8016 KB Output is correct
2 Correct 2 ms 8016 KB Output is correct
3 Incorrect 2 ms 8016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8016 KB Output is correct
2 Correct 2 ms 8016 KB Output is correct
3 Incorrect 2 ms 8016 KB Output isn't correct
4 Halted 0 ms 0 KB -