oj.uz

답안 #417043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
417043 2021-06-03T11:02:52 Z errorgorn Worst Reporter 4 (JOI21_worst_reporter4) C++17
79 / 100
 646 ms 181444 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
int arr[200005];
int h[200005];
int c[200005];

vector<int> al[200005];

map<int,ll> s[200005];

void dfs(int i,int p){
	for (auto &it:al[i]){
		if (it==p) continue;
		
		dfs(it,i);
		if (sz(s[i])<sz(s[it])) swap(s[i],s[it]);
		for (auto &it2:s[it]) s[i][it2.fi]+=it2.se;
	}
	
	s[i][0]+=c[i];
	s[i][h[i]+1]+=c[i];
	s[i][h[i]]-=c[i];
	
	auto iter=s[i].find(h[i]);
	
	while ((*iter).se<0){
		ll temp=min((*prev(iter)).se,-(*iter).se);
		(*iter).se+=temp;
		if ((*prev(iter)).se==temp) s[i].erase(prev(iter));
		else (*prev(iter)).se-=temp;
	}
	
	//cout<<i<<": "<<endl;
	//for (auto &it:s[i]) cout<<it.fi<<" "<<it.se<<endl;
	//cout<<endl;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n;
	rep(x,1,n+1) cin>>arr[x]>>h[x]>>c[x];
	rep(x,2,n+1) al[arr[x]].pub(x);
	
	dfs(1,-1);
	cout<<s[1][0]<<endl;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14372 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14328 KB Output is correct
5 Correct 17 ms 16588 KB Output is correct
6 Correct 15 ms 15636 KB Output is correct
7 Correct 13 ms 15180 KB Output is correct
8 Correct 17 ms 16580 KB Output is correct
9 Correct 14 ms 15564 KB Output is correct
10 Correct 13 ms 15172 KB Output is correct
11 Correct 12 ms 14796 KB Output is correct
12 Correct 12 ms 15284 KB Output is correct
13 Correct 11 ms 15180 KB Output is correct
14 Correct 12 ms 14972 KB Output is correct
15 Correct 12 ms 14924 KB Output is correct
16 Correct 19 ms 17280 KB Output is correct
17 Correct 15 ms 16008 KB Output is correct
18 Correct 11 ms 14768 KB Output is correct
19 Correct 14 ms 15468 KB Output is correct
20 Correct 11 ms 15180 KB Output is correct
21 Correct 11 ms 15052 KB Output is correct
22 Correct 14 ms 15760 KB Output is correct
23 Correct 11 ms 15232 KB Output is correct
24 Correct 14 ms 15436 KB Output is correct
25 Correct 12 ms 15176 KB Output is correct
26 Correct 13 ms 15564 KB Output is correct
27 Correct 14 ms 15564 KB Output is correct
28 Correct 14 ms 15564 KB Output is correct
29 Correct 15 ms 15692 KB Output is correct
30 Correct 14 ms 15876 KB Output is correct
31 Correct 15 ms 15876 KB Output is correct

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14372 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14328 KB Output is correct
5 Correct 17 ms 16588 KB Output is correct
6 Correct 15 ms 15636 KB Output is correct
7 Correct 13 ms 15180 KB Output is correct
8 Correct 17 ms 16580 KB Output is correct
9 Correct 14 ms 15564 KB Output is correct
10 Correct 13 ms 15172 KB Output is correct
11 Correct 12 ms 14796 KB Output is correct
12 Correct 12 ms 15284 KB Output is correct
13 Correct 11 ms 15180 KB Output is correct
14 Correct 12 ms 14972 KB Output is correct
15 Correct 12 ms 14924 KB Output is correct
16 Correct 19 ms 17280 KB Output is correct
17 Correct 15 ms 16008 KB Output is correct
18 Correct 11 ms 14768 KB Output is correct
19 Correct 14 ms 15468 KB Output is correct
20 Correct 11 ms 15180 KB Output is correct
21 Correct 11 ms 15052 KB Output is correct
22 Correct 14 ms 15760 KB Output is correct
23 Correct 11 ms 15232 KB Output is correct
24 Correct 14 ms 15436 KB Output is correct
25 Correct 12 ms 15176 KB Output is correct
26 Correct 13 ms 15564 KB Output is correct
27 Correct 14 ms 15564 KB Output is correct
28 Correct 14 ms 15564 KB Output is correct
29 Correct 15 ms 15692 KB Output is correct
30 Correct 14 ms 15876 KB Output is correct
31 Correct 15 ms 15876 KB Output is correct
32 Correct 17 ms 16560 KB Output is correct
33 Correct 632 ms 131008 KB Output is correct
34 Correct 401 ms 81088 KB Output is correct
35 Correct 571 ms 124896 KB Output is correct
36 Correct 459 ms 81176 KB Output is correct
37 Correct 243 ms 43076 KB Output is correct
38 Correct 205 ms 32488 KB Output is correct
39 Correct 196 ms 48336 KB Output is correct
40 Correct 184 ms 48064 KB Output is correct
41 Correct 117 ms 48048 KB Output is correct
42 Correct 194 ms 35852 KB Output is correct
43 Correct 176 ms 35584 KB Output is correct
44 Correct 646 ms 181444 KB Output is correct
45 Correct 434 ms 110148 KB Output is correct
46 Correct 136 ms 32364 KB Output is correct
47 Correct 396 ms 58860 KB Output is correct
48 Correct 190 ms 45120 KB Output is correct
49 Correct 132 ms 44804 KB Output is correct
50 Correct 388 ms 67564 KB Output is correct
51 Correct 159 ms 42816 KB Output is correct
52 Correct 410 ms 59636 KB Output is correct
53 Correct 166 ms 45416 KB Output is correct
54 Correct 244 ms 60628 KB Output is correct
55 Correct 303 ms 63392 KB Output is correct
56 Correct 248 ms 66056 KB Output is correct
57 Correct 256 ms 68420 KB Output is correct
58 Correct 305 ms 73152 KB Output is correct
59 Correct 312 ms 73052 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14372 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14328 KB Output is correct
5 Correct 17 ms 16588 KB Output is correct
6 Correct 15 ms 15636 KB Output is correct
7 Correct 13 ms 15180 KB Output is correct
8 Correct 17 ms 16580 KB Output is correct
9 Correct 14 ms 15564 KB Output is correct
10 Correct 13 ms 15172 KB Output is correct
11 Correct 12 ms 14796 KB Output is correct
12 Correct 12 ms 15284 KB Output is correct
13 Correct 11 ms 15180 KB Output is correct
14 Correct 12 ms 14972 KB Output is correct
15 Correct 12 ms 14924 KB Output is correct
16 Correct 19 ms 17280 KB Output is correct
17 Correct 15 ms 16008 KB Output is correct
18 Correct 11 ms 14768 KB Output is correct
19 Correct 14 ms 15468 KB Output is correct
20 Correct 11 ms 15180 KB Output is correct
21 Correct 11 ms 15052 KB Output is correct
22 Correct 14 ms 15760 KB Output is correct
23 Correct 11 ms 15232 KB Output is correct
24 Correct 14 ms 15436 KB Output is correct
25 Correct 12 ms 15176 KB Output is correct
26 Correct 13 ms 15564 KB Output is correct
27 Correct 14 ms 15564 KB Output is correct
28 Correct 14 ms 15564 KB Output is correct
29 Correct 15 ms 15692 KB Output is correct
30 Correct 14 ms 15876 KB Output is correct
31 Correct 15 ms 15876 KB Output is correct
32 Correct 17 ms 16560 KB Output is correct
33 Correct 632 ms 131008 KB Output is correct
34 Correct 401 ms 81088 KB Output is correct
35 Correct 571 ms 124896 KB Output is correct
36 Correct 459 ms 81176 KB Output is correct
37 Correct 243 ms 43076 KB Output is correct
38 Correct 205 ms 32488 KB Output is correct
39 Correct 196 ms 48336 KB Output is correct
40 Correct 184 ms 48064 KB Output is correct
41 Correct 117 ms 48048 KB Output is correct
42 Correct 194 ms 35852 KB Output is correct
43 Correct 176 ms 35584 KB Output is correct
44 Correct 646 ms 181444 KB Output is correct
45 Correct 434 ms 110148 KB Output is correct
46 Correct 136 ms 32364 KB Output is correct
47 Correct 396 ms 58860 KB Output is correct
48 Correct 190 ms 45120 KB Output is correct
49 Correct 132 ms 44804 KB Output is correct
50 Correct 388 ms 67564 KB Output is correct
51 Correct 159 ms 42816 KB Output is correct
52 Correct 410 ms 59636 KB Output is correct
53 Correct 166 ms 45416 KB Output is correct
54 Correct 244 ms 60628 KB Output is correct
55 Correct 303 ms 63392 KB Output is correct
56 Correct 248 ms 66056 KB Output is correct
57 Correct 256 ms 68420 KB Output is correct
58 Correct 305 ms 73152 KB Output is correct
59 Correct 312 ms 73052 KB Output is correct
60 Correct 8 ms 14412 KB Output is correct
61 Incorrect 8 ms 14412 KB Output isn't correct
62 Halted 0 ms 0 KB -