oj.uz

Submission #951754

# Submission time Handle Problem Language Result Execution time Memory
951754 2024-03-22T13:22:53 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
6 / 100
 2000 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define int ll

struct node{
	ll x = 0, p = 0;
	node *l = nullptr, *r = nullptr;
	node(){}
};


vector<int> q[200100];
multiset<pii> h[200100];
int n, m, k;
node *d[200100];
int dp[200100][2];

void push(node *v){
	if(!v -> l) v -> l = new node();
	v -> l -> x += v -> p;
	v -> l -> p += v -> p;
	
	if(!v -> r) v -> r = new node();
	v -> r -> x += v -> p;
	v -> r -> p += v -> p;

	v -> p = 0;
}


void upd(node *v, int l, int r, int L, int R, int x){
	if(r < L or R < l){
		return;
	}	
	if(L <= l and r <= R){
		v -> x += x;
		v -> p += x;
		return;
	}
	push(v);
	int mid=(l+r)/2;
	upd(v -> l, l, mid, L, R, x);
	upd(v -> r, mid + 1, r, L, R, x);
	v -> x = max((v -> l ?v -> l -> x :0), (v -> r ?v -> r -> x :0));
}

ll get(node *v, int l, int r, int L, int R){
	if(r < L or R < l){
		return 0;
	}
	if(L <= l and r <= R){
		return v -> x;
	}
	push(v);
	int mid=(l+r)/2;
	ll sum = 0;
	if(v -> l){
		sum = max(sum, get(v -> l, l, mid, L, R));
	}
	if(v -> r){
		sum = max(sum, get(v->r, mid+1, r, L, R));
	}
	return sum;

}


void dfs(int v){
	pii g={-1, -1};
	if(h[v].size()) g = *h[v].begin();
	d[v] = new node(); 
	for(auto to: q[v]){
		dfs(to);
		if(h[to].size() > h[v].size()){
			//swap(h[to], h[v]);
			//swap(d[v], d[to]);
		}
		auto ls = k;
		for(auto dd = h[to].begin(); dd != h[to].end(); dd ++){
			h[v].insert(*dd);
			auto c = dd;
			c++;
			int g;
			if(c == h[to].end()){
				g = k;
			}
			else{
				 g = c -> ff - 1;
			}
			
			//cout<<dd -> ff<<' '<<g<<'\n';
			upd(d[v], 1, k, dd -> ff, g, get(d[to], 1, k, 1, dd -> ff));	
		}                 
		//dp[v][0] += max(dp[to][0], dp[to][1]);
	}
	
	upd(d[v], 1, k, g.ff, g.ff, g.ss);
	if(g.ff != -1){
		//dp[v][1] = get(d[v], 1, k, 1, g.ff);
		
	}
	//cout<<v<<' '<<dp[v][0]<<' '<<dp[v][1]<<'\n';
}


void solve(){    
	cin>>n>>m>>k;
	for(int i=2; i<=n; i++){
		int x;
		cin>>x;
		q[x].pb(i);
	}
	for(int i=1; i<=m; i++){
		int v, l, r;
		cin>>v>>l>>r;
		//dp[v][0] = 1;
		h[v].insert({l, r});
	}
	dfs(1);         
	cout<<get(d[1], 1, k, 1, k);
}


signed main(){
	solve();
}

Compilation message

magictree.cpp: In function 'void dfs(long long int)':
magictree.cpp:83:8: warning: unused variable 'ls' [-Wunused-variable]
   83 |   auto ls = k;
      |        ^~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 68692 KB Output is correct
2 Correct 141 ms 81984 KB Output is correct
3 Correct 130 ms 68904 KB Output is correct
4 Execution timed out 2089 ms 685364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 101964 KB Output is correct
2 Correct 273 ms 91984 KB Output is correct
3 Runtime error 1821 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16988 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16984 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 5 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 432 ms 164052 KB Output is correct
11 Correct 384 ms 138832 KB Output is correct
12 Execution timed out 2087 ms 830736 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 27472 KB Output is correct
2 Correct 61 ms 36000 KB Output is correct
3 Correct 64 ms 36180 KB Output is correct
4 Correct 73 ms 39708 KB Output is correct
5 Correct 23 ms 25536 KB Output is correct
6 Runtime error 1184 ms 1048576 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16988 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16984 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 5 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 129 ms 68692 KB Output is correct
11 Correct 141 ms 81984 KB Output is correct
12 Correct 130 ms 68904 KB Output is correct
13 Execution timed out 2089 ms 685364 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16988 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16984 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 5 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 481 ms 302208 KB Output is correct
11 Runtime error 1654 ms 1048576 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -