oj.uz

Submission #896231

# Submission time Handle Problem Language Result Execution time Memory
896231 2024-01-01T03:52:25 Z 8pete8 Magic Tree (CEOI19_magictree) C++17
34 / 100
 2000 ms 36624 KB 
#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 dp[mxn+10][22],hvy[mxn+10],sz[mxn+10];
pii info[mxn+10];
vector<int>v[mxn+10];
int n,m,k;
int 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].pb(j);
	sort(all(v[cur]));
	if(info[cur].s==0)return;
	auto it=upper_bound(all(v[cur]),info[cur].f);
	int pos=it-v[cur].begin();
	if(it!=v[cur].end())(*it)=info[cur].f;
	else v[cur].pb(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);
	}
	for(int i=0;i<m;i++){
		int v,d,w;cin>>v>>d>>w;
		info[v]={d,w};
	}
	if(k<=20){//sub 1 4 5
		dfs(1,-1);
		for(int i=0;i<=k;i++)ans=max(ans,dp[1][i]);
		cout<<ans;
	}
	else{
		//sub w=1
		init(1,-1);
		solve(1,-1);
		cout<<v[1].size();
	}
	return 0;
}

Compilation message

magictree.cpp: In function 'void solve(long long int, long long int)':
magictree.cpp:65:6: warning: unused variable 'pos' [-Wunused-variable]
   65 |  int pos=it-v[cur].begin();
      |      ^~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 38 ms 25660 KB Output is correct
5 Execution timed out 2055 ms 26012 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 27220 KB Output is correct
2 Correct 38 ms 27216 KB Output is correct
3 Correct 37 ms 31024 KB Output is correct
4 Correct 24 ms 26328 KB Output is correct
5 Correct 37 ms 36624 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 2 ms 11096 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 45 ms 26136 KB Output is correct
11 Correct 44 ms 26420 KB Output is correct
12 Correct 42 ms 31056 KB Output is correct
13 Correct 25 ms 26320 KB Output is correct
14 Correct 35 ms 35156 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 2 ms 11096 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 3 ms 9052 KB Output is correct
13 Correct 38 ms 25660 KB Output is correct
14 Execution timed out 2055 ms 26012 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 2 ms 11096 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Incorrect 34 ms 15880 KB Output isn't correct
11 Halted 0 ms 0 KB -