oj.uz

Submission #932914

# Submission time Handle Problem Language Result Execution time Memory
932914 2024-02-24T13:54:51 Z beepbeepsheep Magic Tree (CEOI19_magictree) C++17
16 / 100
 137 ms 38664 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>

const ll maxn=1e5+5;
const ll inf=1e15; 

vector<ll> adj[maxn];
set<ii> s[maxn];
ii arr[maxn];

void dfs(ll x){
	for (auto u:adj[x]){
		dfs(u);
		if (s[u].size()>s[x].size()) swap(s[u],s[x]);
		for (auto [a,b]:s[u]) s[x].emplace(a,b);
	}
	ll pos,cnt;
	tie(pos,cnt)=arr[x];
	while (cnt){
		ll p,c;
		if (s[x].lower_bound(make_pair(pos,inf))==s[x].end()) break;
		tie(p,c)=*s[x].lower_bound(make_pair(pos,inf));
		if (cnt>=c){
			cnt-=c;
			s[x].erase(make_pair(p,c));
		} else{
			s[x].erase(make_pair(p,c));
			c-=cnt;
			cnt=0;
			s[x].emplace(p,c);
		}
	}
	s[x].emplace(arr[x]);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n,k,m,a,b,c;
	cin>>n>>k>>m;
	for (int i=2;i<=n;i++){
		cin>>a;
		adj[a].emplace_back(i);
	}
	for (int i=1;i<=k;i++){
		cin>>a>>b>>c; //pos, time, value
		arr[a]={b,c};
	}
	dfs(1);
	ll ans=0;
	for (auto [u,v]:s[1]) ans+=v;
	cout<<ans; 
	return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 21332 KB Output is correct
2 Correct 32 ms 20828 KB Output is correct
3 Correct 104 ms 38664 KB Output is correct
4 Correct 62 ms 21708 KB Output is correct
5 Correct 137 ms 22924 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

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

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10076 KB Output is correct
2 Correct 22 ms 14172 KB Output is correct
3 Correct 23 ms 14160 KB Output is correct
4 Correct 24 ms 14164 KB Output is correct
5 Correct 15 ms 16088 KB Output is correct
6 Correct 27 ms 17492 KB Output is correct
7 Correct 24 ms 19028 KB Output is correct

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

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