oj.uz

Submission #833956

# Submission time Handle Problem Language Result Execution time Memory
833956 2023-08-22T09:46:49 Z MODDI Magic Tree (CEOI19_magictree) C++14
68 / 100
 114 ms 29464 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m, k;
vi G[100100];
vector<pll> fruits;
map<int, int> dp[100100];
void dfs(int node, int p){
//	cout<<"AT: "<<node<<endl;
	for(auto next : G[node]){
		if(next !=p){
			dfs(next, node);
			if(dp[node].size() < dp[next].size()) swap(dp[node], dp[next]);
			for(auto t : dp[next])	dp[node][t.first] += t.second;
		}
	}
	if(fruits[node].first != -1){
		ll hold = fruits[node].second;
		while(hold > 0){
			auto rem = dp[node].upper_bound(fruits[node].first);
			if(rem == dp[node].end())	break;
			if(rem->second <= hold){
				hold -= rem->second;
				dp[node].erase(rem);
			}
			else{
				rem->second -= hold;
				break;
			}
		}
		dp[node][fruits[node].first] += fruits[node].second;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>k;
	for(int i = 2; i <= n; i++){
		int a;
		cin>>a;
		G[a-1].pb(i-1);
		G[i-1].pb(a-1);
	}
	fruits.resize(n+1);
	for(int i = 0; i < n; i++)
		fruits[i] = mp(-1, -1);
	for(int i = 0; i < m; i++){
		int node, day, add;
		cin>>node>>day>>add;
		node--;
		fruits[node] = mp(day, add);
	}
	ll ans = 0;
	dfs(0, -1);
//	cout<<dp[0].size()<<endl;
	for(auto t : dp[0])	ans += t.second;
	
	cout<<ans<<endl;
	return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7508 KB Output is correct
2 Correct 3 ms 7508 KB Output is correct
3 Correct 3 ms 7508 KB Output is correct
4 Correct 48 ms 26520 KB Output is correct
5 Correct 66 ms 29464 KB Output is correct
6 Correct 61 ms 26520 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 4 ms 7320 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 3 ms 7252 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 3 ms 7252 KB Output is correct
10 Correct 71 ms 16976 KB Output is correct
11 Correct 77 ms 16312 KB Output is correct
12 Correct 45 ms 17852 KB Output is correct
13 Correct 32 ms 17812 KB Output is correct
14 Correct 41 ms 26096 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8408 KB Output is correct
2 Correct 28 ms 12208 KB Output is correct
3 Correct 27 ms 12336 KB Output is correct
4 Correct 24 ms 12372 KB Output is correct
5 Correct 16 ms 12532 KB Output is correct
6 Correct 30 ms 14724 KB Output is correct
7 Correct 24 ms 17108 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 4 ms 7320 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 3 ms 7252 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 3 ms 7252 KB Output is correct
10 Correct 3 ms 7508 KB Output is correct
11 Correct 3 ms 7508 KB Output is correct
12 Correct 3 ms 7508 KB Output is correct
13 Correct 48 ms 26520 KB Output is correct
14 Correct 66 ms 29464 KB Output is correct
15 Correct 61 ms 26520 KB Output is correct
16 Correct 71 ms 16976 KB Output is correct
17 Correct 77 ms 16312 KB Output is correct
18 Correct 45 ms 17852 KB Output is correct
19 Correct 32 ms 17812 KB Output is correct
20 Correct 41 ms 26096 KB Output is correct
21 Correct 21 ms 10572 KB Output is correct
22 Correct 62 ms 19212 KB Output is correct
23 Correct 70 ms 21604 KB Output is correct
24 Correct 114 ms 27948 KB Output is correct
25 Correct 62 ms 20872 KB Output is correct
26 Correct 89 ms 21964 KB Output is correct
27 Correct 63 ms 20840 KB Output is correct

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 4 ms 7320 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 3 ms 7252 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 3 ms 7252 KB Output is correct
10 Incorrect 53 ms 18048 KB Output isn't correct
11 Halted 0 ms 0 KB -