Submission #896237

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
896237	2024-01-01T04:03:47 Z	8pete8	Magic Tree (CEOI19_magictree)	C++17	70 / 100	471 ms	1048576 KB

magictree

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<float.h>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
//#define int long long
#define double long double
const int mod=998244353,mxn=1e5,lg=22;//inf=1e18,minf=-1e18,Mxn=100000;
vector<int>adj[mxn+10];
int hvy[mxn+10],sz[mxn+10],sum[mxn+10];
vector<vector<ll>>dp;
pii info[mxn+10];
multiset<int>v[mxn+10];
int n,m,k;
ll ans=0;
void init(int cur,int p){
	sz[cur]=1;
	for(auto i:adj[cur]){
		init(i,cur);
		sz[cur]+=sz[i];
	}
	for(auto i:adj[cur])if(sz[hvy[cur]]<sz[i])hvy[cur]=i;
}
void dfs(int cur,int p){
	for(auto i:adj[cur])dfs(i,cur);
	for(auto i:adj[cur])for(int j=0;j<=k;j++)dp[cur][j]+=dp[i][j];
	dp[cur][info[cur].f]+=info[cur].s;
	for(int j=1;j<=k;j++)dp[cur][j]=max(dp[cur][j],dp[cur][j-1]);
}
void solve(int cur,int p){
	for(auto i:adj[cur])solve(i,cur);
	if(hvy[cur])swap(v[cur],v[hvy[cur]]);
	for(auto i:adj[cur])if(i!=hvy[cur])for(auto j:v[i])v[cur].insert(j);
	if(info[cur].s==0)return;
	auto it=v[cur].upper_bound(info[cur].f);
	if(it!=v[cur].end())v[cur].erase(it);
	v[cur].insert(info[cur].f);
}
int32_t main(){
    fastio
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++){
		int p;cin>>p;
		adj[p].pb(i);
	}
	bool yes=true;
	for(int i=0;i<m;i++){
		int v,d,w;cin>>v>>d>>w;
		info[v]={d,w};
		ans+=w;
		if(w!=1)yes=false;
	}
	if(yes){//w=1
		init(1,-1);
		solve(1,-1);
		cout<<v[1].size();
	}
	else if(k<=20||m<=1000){
		dp.resize(n+1,vector<ll>(k+1));
		dfs(1,-1);
		ans=0;
		for(int i=0;i<=k;i++)ans=max(ans,dp[1][i]);
		cout<<ans;
	}
	else{//sub 2
		cout<<ans;
	}
	return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	10844 KB	Output is correct
2	Correct	15 ms	11868 KB	Output is correct
3	Correct	34 ms	10168 KB	Output is correct
4	Correct	23 ms	9952 KB	Output is correct
5	Correct	27 ms	10192 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	9564 KB	Output is correct
2	Correct	2 ms	9564 KB	Output is correct
3	Correct	3 ms	9564 KB	Output is correct
4	Correct	40 ms	23640 KB	Output is correct
5	Correct	55 ms	28136 KB	Output is correct
6	Correct	48 ms	23808 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	16448 KB	Output is correct
2	Correct	37 ms	16336 KB	Output is correct
3	Correct	45 ms	20752 KB	Output is correct
4	Correct	27 ms	15312 KB	Output is correct
5	Correct	35 ms	25680 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	9308 KB	Output is correct
2	Correct	3 ms	9308 KB	Output is correct
3	Correct	2 ms	9308 KB	Output is correct
4	Correct	2 ms	9308 KB	Output is correct
5	Correct	2 ms	9308 KB	Output is correct
6	Correct	2 ms	9432 KB	Output is correct
7	Correct	2 ms	9308 KB	Output is correct
8	Correct	2 ms	9308 KB	Output is correct
9	Correct	2 ms	9308 KB	Output is correct
10	Correct	74 ms	25940 KB	Output is correct
11	Correct	83 ms	26396 KB	Output is correct
12	Correct	49 ms	18516 KB	Output is correct
13	Correct	37 ms	18128 KB	Output is correct
14	Correct	45 ms	23640 KB	Output is correct

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	471 ms	1048576 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #7
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	9308 KB	Output is correct
2	Correct	3 ms	9308 KB	Output is correct
3	Correct	2 ms	9308 KB	Output is correct
4	Correct	2 ms	9308 KB	Output is correct
5	Correct	2 ms	9308 KB	Output is correct
6	Correct	2 ms	9432 KB	Output is correct
7	Correct	2 ms	9308 KB	Output is correct
8	Correct	2 ms	9308 KB	Output is correct
9	Correct	2 ms	9308 KB	Output is correct
10	Correct	2 ms	9564 KB	Output is correct
11	Correct	2 ms	9564 KB	Output is correct
12	Correct	3 ms	9564 KB	Output is correct
13	Correct	40 ms	23640 KB	Output is correct
14	Correct	55 ms	28136 KB	Output is correct
15	Correct	48 ms	23808 KB	Output is correct
16	Correct	74 ms	25940 KB	Output is correct
17	Correct	83 ms	26396 KB	Output is correct
18	Correct	49 ms	18516 KB	Output is correct
19	Correct	37 ms	18128 KB	Output is correct
20	Correct	45 ms	23640 KB	Output is correct
21	Correct	22 ms	12648 KB	Output is correct
22	Correct	53 ms	20296 KB	Output is correct
23	Correct	55 ms	20428 KB	Output is correct
24	Correct	82 ms	26952 KB	Output is correct
25	Correct	45 ms	19160 KB	Output is correct
26	Correct	72 ms	20208 KB	Output is correct
27	Correct	53 ms	19248 KB	Output is correct

Subtask #8
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	9308 KB	Output is correct
2	Correct	3 ms	9308 KB	Output is correct
3	Correct	2 ms	9308 KB	Output is correct
4	Correct	2 ms	9308 KB	Output is correct
5	Correct	2 ms	9308 KB	Output is correct
6	Correct	2 ms	9432 KB	Output is correct
7	Correct	2 ms	9308 KB	Output is correct
8	Correct	2 ms	9308 KB	Output is correct
9	Correct	2 ms	9308 KB	Output is correct
10	Correct	17 ms	10844 KB	Output is correct
11	Correct	15 ms	11868 KB	Output is correct
12	Correct	34 ms	10168 KB	Output is correct
13	Correct	23 ms	9952 KB	Output is correct
14	Correct	27 ms	10192 KB	Output is correct
15	Correct	2 ms	9564 KB	Output is correct
16	Correct	2 ms	9564 KB	Output is correct
17	Correct	3 ms	9564 KB	Output is correct
18	Correct	40 ms	23640 KB	Output is correct
19	Correct	55 ms	28136 KB	Output is correct
20	Correct	48 ms	23808 KB	Output is correct
21	Correct	38 ms	16448 KB	Output is correct
22	Correct	37 ms	16336 KB	Output is correct
23	Correct	45 ms	20752 KB	Output is correct
24	Correct	27 ms	15312 KB	Output is correct
25	Correct	35 ms	25680 KB	Output is correct
26	Correct	74 ms	25940 KB	Output is correct
27	Correct	83 ms	26396 KB	Output is correct
28	Correct	49 ms	18516 KB	Output is correct
29	Correct	37 ms	18128 KB	Output is correct
30	Correct	45 ms	23640 KB	Output is correct
31	Runtime error	471 ms	1048576 KB	Execution killed with signal 9
32	Halted	0 ms	0 KB	-

Submission #896237

Compilation message