oj.uz

Submission #518927

# Submission time Handle Problem Language Result Execution time Memory
518927 2022-01-25T08:05:45 Z Keshi Worst Reporter 4 (JOI21_worst_reporter4) C++17
0 / 100
 13 ms 15624 KB 
//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
const int inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll pw(ll a, ll b){
	ll c = 1;
	while(b){
		if(b & 1) c = c * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return c;
}

int n, a[maxn], h[maxn], c[maxn];
vector<int> g[maxn];
vector<int> vec;
set<pll> s[maxn];

void solve(int v){
	for(int u : g[v]){
		solve(u);
		if(Sz(s[u]) > Sz(s[v])) s[v].swap(s[u]);
		for(auto x : s[u]){
			s[v].insert(x);
		}
	}
/*	cout << "# " << v << "\n";
	for(auto i : s[v]){
		cout << "  " << i.F << " " << i.S << "\n";
	}
	cout << "! " << h[v] << " " << c[v] << "\n";*/
	auto it = s[v].lower_bound(Mp(h[v], -inf));
	ll x = c[v];
	while(it != s[v].end() && it -> S <= x){
		x -= it->S;
		it = s[v].erase(it);
	}
	if(it != s[v].end()){
		auto i = *it;
		s[v].erase(it);
		s[v].insert(Mp(i.F, i.S - x));
	}
	s[v].insert(Mp(h[v], c[v]));
	/*for(auto i : s[v]){
		cout << "  " << i.F << " " << i.S << "\n";
	}
	cout << "\n";*/
	return;
}

int main(){
	fast_io;
	
	cin >> n;
	ll sc = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> h[i] >> c[i];
		vec.pb(h[i]);
		if(i != 1) g[a[i]].pb(i);
		sc += c[i];
	}
	sort(all(vec));
	vec.resize(unique(all(vec)) - vec.begin());
	for(int i = 1; i <= n; i++){
		h[i] = Sz(vec) - 1 - (lower_bound(all(vec), h[i]) - vec.begin());
	}
	solve(1);
	for(auto i : s[1]){
//		cout << i.F << " " << i.S << "\n";
		sc -= i.S;
	}
	cout << sc << "\n";
	
	return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 10 ms 14416 KB Output is correct
5 Correct 13 ms 15580 KB Output is correct
6 Incorrect 13 ms 15624 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 10 ms 14416 KB Output is correct
5 Correct 13 ms 15580 KB Output is correct
6 Incorrect 13 ms 15624 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 10 ms 14416 KB Output is correct
5 Correct 13 ms 15580 KB Output is correct
6 Incorrect 13 ms 15624 KB Output isn't correct
7 Halted 0 ms 0 KB -