oj.uz

답안 #980493

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
980493 2024-05-12T08:00:26 Z happy_node Worst Reporter 4 (JOI21_worst_reporter4) C++17
0 / 100
 16 ms 33880 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=2e5+5;
int N;
int A[MX],H[MX],C[MX];

vector<int> adj[MX];

multiset<pair<ll,ll>> dp[MX];
int par[MX];

int find(int v) {
	return par[v]==v?v:par[v]=find(par[v]);
}

void merge(int u, int v) {
	u=find(u),v=find(v);
	if(u==v) return;

	if(dp[u].size()>dp[v].size()) swap(u,v);

	for(auto [pos,val]:dp[u]) {
		auto it=dp[v].lower_bound(make_pair(pos,0));
		dp[v].insert({pos,val});
	}

	par[u]=v;
	dp[u].clear();
}

void dfs(int v, int p) {
	int prv=-1;
	for(auto u:adj[v]) {
		if(u==p) continue;
		dfs(u,v);
		if(prv!=-1) 
			merge(u,prv);
		prv=u;
	}

	if(prv!=-1) merge(v,prv);

	int pv=find(v);

	auto it=dp[pv].lower_bound(make_pair(H[v],0));

	if(it==dp[pv].begin()) {
		dp[pv].insert(make_pair(H[v],C[v]));
	} else {
		it--;
		ll cur=C[v];
		while(true) {
			if(cur>=it->second) {
 				cur-=it->second;
 				if(it==dp[pv].begin()) {
 					dp[pv].erase(it);
 					break;
 				} else {
 					it=dp[prv].erase(it);
 				}
			} else {
				dp[pv].insert({it->first,it->second-cur});
				dp[pv].erase(it);
				cur=0;
				break;
			}
		}
		dp[pv].insert(make_pair(H[v],C[v]));
	}
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N;
	ll sum=0;
	for(int i=1;i<=N;i++) {
		cin>>A[i]>>H[i]>>C[i];
		sum+=C[i];
	}

	for(int i=2;i<=N;i++) {
		adj[A[i]].push_back(i);
	}

	for(int i=1;i<=N;i++) par[i]=i;
	dfs(1,0);

	ll ans=0;
	for(auto [pos,val]:dp[find(1)]) {
		ans+=val;
	}

	cout<<sum-ans<<'\n';
}

Compilation message

worst_reporter2.cpp: In function 'void merge(int, int)':
worst_reporter2.cpp:26:8: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   26 |   auto it=dp[v].lower_bound(make_pair(pos,0));
      |        ^~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 3 ms 16728 KB Output is correct
3 Runtime error 16 ms 33880 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 3 ms 16728 KB Output is correct
3 Runtime error 16 ms 33880 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 3 ms 16728 KB Output is correct
3 Runtime error 16 ms 33880 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -