oj.uz

Submission #579386

# Submission time Handle Problem Language Result Execution time Memory
579386 2022-06-19T04:18:07 Z amunduzbaev Magic Tree (CEOI19_magictree) C++17
15 / 100
 817 ms 1048576 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll
 
const int N = 1e5 + 5;
vector<int> edges[N];
int is[N], d[N], w[N], mx[N];
map<int, int> sub[N];
 
void dfs(int u){
	mx[u] = u;
	for(auto x : edges[u]){
		dfs(x);
		if(sub[x].size() > sub[mx[u]].size()) mx[u] = x;
	}
	
	swap(sub[u], sub[mx[u]]);
	for(auto x : edges[u]){
		if(x == mx[u]) continue;
		for(auto v : sub[x]){
			sub[u][v.first] += v.second;
		}
		sub[x].clear();
	}
	
	if(is[u]){
		sub[u][d[u]] += w[u];
		auto it = sub[u].upper_bound(d[u]);
		vector<int> er;
		int sum = 0;
		while(it != sub[u].end()){
			sum += (*it).second;
			if(sum >= w[u]){
				sub[u][(*it).first] = sum - w[u];
				break;
			}
			er.push_back((*it).first);
		}
		
		for(auto x : er){
			sub[u].erase(x);
		}
	}
}
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m, k; cin>>n>>m>>k;
	for(int i=2;i<=n;i++){
		int x; cin>>x;
		edges[x].push_back(i);
	}
	
	for(int i=0;i<m;i++){
		int v; cin>>v;
		cin>>d[v]>>w[v];
		is[v] = 1;
	}
	
	dfs(1);
	int sum = 0;
	for(auto x : sub[1]) sum += x.second;
	cout<<sum<<"\n";
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Runtime error 817 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 14168 KB Output is correct
2 Correct 54 ms 19088 KB Output is correct
3 Correct 117 ms 17588 KB Output is correct
4 Correct 75 ms 16792 KB Output is correct
5 Correct 111 ms 16760 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 12408 KB Output is correct
2 Correct 60 ms 12236 KB Output is correct
3 Correct 51 ms 19312 KB Output is correct
4 Correct 48 ms 16864 KB Output is correct
5 Correct 62 ms 29240 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Runtime error 817 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Runtime error 817 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Runtime error 817 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -