oj.uz

Submission #518948

# Submission time Handle Problem Language Result Execution time Memory
518948 2022-01-25T09:00:36 Z Keshi Worst Reporter 4 (JOI21_worst_reporter4) C++17
100 / 100
 378 ms 134616 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;
}

ll n, a[maxn], h[maxn], c[maxn], pp[maxn], ptr;
bool ind[maxn], vis[maxn];
int vs[maxn];
vector<int> g[maxn];
vector<int> vec;
set<pll> s[maxn];

void solve(int v){
	vis[v] = 1;
	for(int u : g[v]){
		if(vis[u]) continue;
//		cout << "# " << v << " -> " << u << "\n";
		solve(u);
		if(Sz(s[u]) > Sz(s[v])) s[v].swap(s[u]);
		for(auto x : s[u]){
			s[v].insert(x);
		}
	}
	if(ind[v]) return;
//	cout << " ########## " << v << "\n";
	auto it = s[v].lower_bound(Mp(h[v], inf));
	ll x = c[v];
	while(it != s[v].end() && pp[it -> S] <= x){
		x -= pp[it->S];
		it = s[v].erase(it);
	}
	if(it != s[v].end()){
		pp[it->S] -= x;
	}
	pp[ptr] = c[v];
	s[v].insert(Mp(h[v], ptr++));
	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]);
		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());
	}
	for(int i = 1; i <= n; i++){
		int v = i;
		while(vs[v] == 0){
			vs[v] = i;
			v = a[v];
		}
		if(vs[v] != i) continue;
		int u = v;
		map<ll, ll> mp;
		do{
			ind[u] = 1;
//			cout << "^ " << u << " " << h[u] << " " << c[u] << "\n";
			mp[h[u]] += c[u];
			u = a[u];
		}while(v != u);
		solve(v);
		ll x = 0, y = 0;
		for(auto j : s[v]){
//			cout << " * " << j.F << " " << pp[j.S] << "\n";
			x += pp[j.S];
		}
		auto it = s[v].begin();
		ll mx = x;
		for(auto j : mp){
			while(it != s[v].end() && it->F <= j.F){
				y += pp[it->S];
				it++;
			}
			mx = max(mx, y + j.S);
//			cout << " ? " << j.F << " " << j.S << " -> " << y << "\n";
		}
//		cout << "$ " << mx << " " << x << "\n";
		sc -= mx;
	}
	cout << sc << "\n";
	
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 8 ms 14392 KB Output is correct
5 Correct 13 ms 15688 KB Output is correct
6 Correct 16 ms 15812 KB Output is correct
7 Correct 13 ms 15764 KB Output is correct
8 Correct 15 ms 15832 KB Output is correct
9 Correct 13 ms 15828 KB Output is correct
10 Correct 12 ms 15820 KB Output is correct
11 Correct 13 ms 16068 KB Output is correct
12 Correct 11 ms 15560 KB Output is correct
13 Correct 11 ms 15600 KB Output is correct
14 Correct 10 ms 15196 KB Output is correct
15 Correct 11 ms 15284 KB Output is correct
16 Correct 15 ms 16220 KB Output is correct
17 Correct 14 ms 16160 KB Output is correct
18 Correct 16 ms 16640 KB Output is correct
19 Correct 14 ms 15448 KB Output is correct
20 Correct 12 ms 15428 KB Output is correct
21 Correct 11 ms 15432 KB Output is correct
22 Correct 11 ms 15304 KB Output is correct
23 Correct 12 ms 15432 KB Output is correct
24 Correct 11 ms 15532 KB Output is correct
25 Correct 14 ms 15452 KB Output is correct
26 Correct 10 ms 15568 KB Output is correct
27 Correct 11 ms 15436 KB Output is correct
28 Correct 11 ms 15596 KB Output is correct
29 Correct 11 ms 15704 KB Output is correct
30 Correct 11 ms 15740 KB Output is correct
31 Correct 12 ms 15668 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 8 ms 14392 KB Output is correct
5 Correct 13 ms 15688 KB Output is correct
6 Correct 16 ms 15812 KB Output is correct
7 Correct 13 ms 15764 KB Output is correct
8 Correct 15 ms 15832 KB Output is correct
9 Correct 13 ms 15828 KB Output is correct
10 Correct 12 ms 15820 KB Output is correct
11 Correct 13 ms 16068 KB Output is correct
12 Correct 11 ms 15560 KB Output is correct
13 Correct 11 ms 15600 KB Output is correct
14 Correct 10 ms 15196 KB Output is correct
15 Correct 11 ms 15284 KB Output is correct
16 Correct 15 ms 16220 KB Output is correct
17 Correct 14 ms 16160 KB Output is correct
18 Correct 16 ms 16640 KB Output is correct
19 Correct 14 ms 15448 KB Output is correct
20 Correct 12 ms 15428 KB Output is correct
21 Correct 11 ms 15432 KB Output is correct
22 Correct 11 ms 15304 KB Output is correct
23 Correct 12 ms 15432 KB Output is correct
24 Correct 11 ms 15532 KB Output is correct
25 Correct 14 ms 15452 KB Output is correct
26 Correct 10 ms 15568 KB Output is correct
27 Correct 11 ms 15436 KB Output is correct
28 Correct 11 ms 15596 KB Output is correct
29 Correct 11 ms 15704 KB Output is correct
30 Correct 11 ms 15740 KB Output is correct
31 Correct 12 ms 15668 KB Output is correct
32 Correct 13 ms 15812 KB Output is correct
33 Correct 342 ms 82880 KB Output is correct
34 Correct 334 ms 82464 KB Output is correct
35 Correct 348 ms 79776 KB Output is correct
36 Correct 347 ms 82604 KB Output is correct
37 Correct 304 ms 84000 KB Output is correct
38 Correct 368 ms 93892 KB Output is correct
39 Correct 189 ms 59076 KB Output is correct
40 Correct 173 ms 58496 KB Output is correct
41 Correct 146 ms 60312 KB Output is correct
42 Correct 209 ms 43676 KB Output is correct
43 Correct 151 ms 43624 KB Output is correct
44 Correct 338 ms 105888 KB Output is correct
45 Correct 325 ms 105952 KB Output is correct
46 Correct 378 ms 134616 KB Output is correct
47 Correct 264 ms 53572 KB Output is correct
48 Correct 243 ms 52980 KB Output is correct
49 Correct 171 ms 54072 KB Output is correct
50 Correct 283 ms 48940 KB Output is correct
51 Correct 234 ms 48908 KB Output is correct
52 Correct 317 ms 54324 KB Output is correct
53 Correct 254 ms 53380 KB Output is correct
54 Correct 114 ms 57528 KB Output is correct
55 Correct 218 ms 56048 KB Output is correct
56 Correct 182 ms 62008 KB Output is correct
57 Correct 172 ms 64952 KB Output is correct
58 Correct 194 ms 62264 KB Output is correct
59 Correct 202 ms 62224 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 8 ms 14392 KB Output is correct
5 Correct 13 ms 15688 KB Output is correct
6 Correct 16 ms 15812 KB Output is correct
7 Correct 13 ms 15764 KB Output is correct
8 Correct 15 ms 15832 KB Output is correct
9 Correct 13 ms 15828 KB Output is correct
10 Correct 12 ms 15820 KB Output is correct
11 Correct 13 ms 16068 KB Output is correct
12 Correct 11 ms 15560 KB Output is correct
13 Correct 11 ms 15600 KB Output is correct
14 Correct 10 ms 15196 KB Output is correct
15 Correct 11 ms 15284 KB Output is correct
16 Correct 15 ms 16220 KB Output is correct
17 Correct 14 ms 16160 KB Output is correct
18 Correct 16 ms 16640 KB Output is correct
19 Correct 14 ms 15448 KB Output is correct
20 Correct 12 ms 15428 KB Output is correct
21 Correct 11 ms 15432 KB Output is correct
22 Correct 11 ms 15304 KB Output is correct
23 Correct 12 ms 15432 KB Output is correct
24 Correct 11 ms 15532 KB Output is correct
25 Correct 14 ms 15452 KB Output is correct
26 Correct 10 ms 15568 KB Output is correct
27 Correct 11 ms 15436 KB Output is correct
28 Correct 11 ms 15596 KB Output is correct
29 Correct 11 ms 15704 KB Output is correct
30 Correct 11 ms 15740 KB Output is correct
31 Correct 12 ms 15668 KB Output is correct
32 Correct 13 ms 15812 KB Output is correct
33 Correct 342 ms 82880 KB Output is correct
34 Correct 334 ms 82464 KB Output is correct
35 Correct 348 ms 79776 KB Output is correct
36 Correct 347 ms 82604 KB Output is correct
37 Correct 304 ms 84000 KB Output is correct
38 Correct 368 ms 93892 KB Output is correct
39 Correct 189 ms 59076 KB Output is correct
40 Correct 173 ms 58496 KB Output is correct
41 Correct 146 ms 60312 KB Output is correct
42 Correct 209 ms 43676 KB Output is correct
43 Correct 151 ms 43624 KB Output is correct
44 Correct 338 ms 105888 KB Output is correct
45 Correct 325 ms 105952 KB Output is correct
46 Correct 378 ms 134616 KB Output is correct
47 Correct 264 ms 53572 KB Output is correct
48 Correct 243 ms 52980 KB Output is correct
49 Correct 171 ms 54072 KB Output is correct
50 Correct 283 ms 48940 KB Output is correct
51 Correct 234 ms 48908 KB Output is correct
52 Correct 317 ms 54324 KB Output is correct
53 Correct 254 ms 53380 KB Output is correct
54 Correct 114 ms 57528 KB Output is correct
55 Correct 218 ms 56048 KB Output is correct
56 Correct 182 ms 62008 KB Output is correct
57 Correct 172 ms 64952 KB Output is correct
58 Correct 194 ms 62264 KB Output is correct
59 Correct 202 ms 62224 KB Output is correct
60 Correct 7 ms 14376 KB Output is correct
61 Correct 7 ms 14412 KB Output is correct
62 Correct 7 ms 14412 KB Output is correct
63 Correct 8 ms 14412 KB Output is correct
64 Correct 332 ms 70484 KB Output is correct
65 Correct 317 ms 69912 KB Output is correct
66 Correct 325 ms 69848 KB Output is correct
67 Correct 314 ms 69160 KB Output is correct
68 Correct 290 ms 71040 KB Output is correct
69 Correct 299 ms 82448 KB Output is correct
70 Correct 296 ms 60392 KB Output is correct
71 Correct 190 ms 46896 KB Output is correct
72 Correct 322 ms 73088 KB Output is correct
73 Correct 183 ms 60668 KB Output is correct
74 Correct 343 ms 62900 KB Output is correct
75 Correct 288 ms 56732 KB Output is correct
76 Correct 211 ms 56764 KB Output is correct
77 Correct 307 ms 63384 KB Output is correct
78 Correct 225 ms 57140 KB Output is correct
79 Correct 322 ms 79036 KB Output is correct
80 Correct 266 ms 73136 KB Output is correct
81 Correct 258 ms 74620 KB Output is correct
82 Correct 231 ms 73352 KB Output is correct
83 Correct 127 ms 32436 KB Output is correct
84 Correct 284 ms 60828 KB Output is correct
85 Correct 297 ms 60896 KB Output is correct
86 Correct 291 ms 64076 KB Output is correct
87 Correct 284 ms 60796 KB Output is correct
88 Correct 303 ms 60940 KB Output is correct