oj.uz

답안 #519557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
519557 2022-01-26T16:34:54 Z fatemetmhr Worst Reporter 4 (JOI21_worst_reporter4) C++17
79 / 100
 1980 ms 176768 KB 
//  ~Be name khoda~  //
 
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'
 
const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1e6   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;
 
struct seg{
 
	ll set, add;
	seg(){
		set = -1;
		add = 0;
	}
	
	inline void clear(){
		set = -1;
		add = 0;
	}
	
}node[maxnt];
 
int m, ver[maxn5];
vector <pair<int, ll>> have[maxn5];
vector <int> ex, ch, adj[maxn5], av;
int sz[maxn5], big[maxn5], st[maxn5], ft[maxn5];
int ti = -1, h[maxn5];
ll c[maxn5];
 
inline void shift(int v){
	if(node[v].set != -1){
		node[v * 2].set = node[v * 2 + 1].set = node[v].set;
		node[v].set = -1;
		node[v * 2].add = node[v * 2 + 1].add = 0;
	}
	node[v * 2].add += node[v].add;
	node[v * 2 + 1].add += node[v].add;
	node[v].add = 0;
	ch.pb(v * 2);
	ch.pb(v * 2 + 1);
	return;
}
 
inline void sset(int l, int r, int lq, int rq, ll val, int v){
	if(rq <= l || r <= lq)
		return;
	if(lq <= l && r <= rq){
		node[v].set = val;
		node[v].add = 0;
		return;
	}
	int mid = (l + r) >> 1; shift(v);
	sset(l, mid, lq, rq, val, v * 2);
	sset(mid, r, lq, rq, val, v * 2 + 1);
	return;
}
 
inline void add(int l, int r, int lq, int rq, ll val, int v){
	if(rq <= l || r <= lq)
		return;
	if(lq <= l && r <= rq){
		node[v].add += val;
		return;
	}
	int mid = (l + r) >> 1; shift(v);
	add(l, mid, lq, rq, val, v * 2);
	add(mid, r, lq, rq, val, v * 2 + 1);
	return;
}
 
inline ll get(int l, int r, int ind, int v){
	if(node[v].set > -1)
		return node[v].set + node[v].add;
	if(r - l == 1)
		return node[v].add;
	int mid = (l + r) >> 1;
	if(ind < mid)
		return get(l, mid, ind, v * 2) + node[v].add;
	return get(mid, r, ind, v * 2 + 1) + node[v].add;
}
 
inline void upd(int id, ll val){
	int lo = -1, hi = id + 1;
	while(hi - lo > 1){
		int mid = (lo + hi) >> 1;
		if(get(0, m, mid, 1) < val)
			hi = mid;
		else
			lo = mid;
	}
	if(hi > id)
		return;
	sset(0, m, hi, id + 1, val, 1);
	//cout << "found out " << id << ' ' << val << ' ' << hi << endl;
	return;
}
 
inline void dfs_det(int v){
	sz[v] = 1;
	big[v] = -1;
	st[v] = ++ti;
	ver[ti] = v;
	for(auto u : adj[v]){
		dfs_det(u);
		sz[v] += sz[u];
		if(big[v] == -1 || sz[u] >= sz[big[v]])
			big[v] = u;
	}
	ft[v] = ti;
	return;
}
 
inline void dfs(int v, bool keep){
	for(auto u : adj[v]) if(big[v] != u)
		dfs(u, false);
	if(big[v] == -1){
		if(keep){
			sset(0, m, 0, h[v] + 1, c[v], 1);
		}
		else{
			have[v].pb({0, c[v]});
			if(h[v] + 1 < m)
				have[v].pb({h[v] + 1, 0});
		}
		return;
	}
	dfs(big[v], true);
	for(auto u : adj[v]) if(u != big[v]){
		for(int i = 0; i < have[u].size(); i++){
			int st = have[u][i].fi;
			ll val = have[u][i].se;
			int ft = m;
			if(i + 1 < have[u].size())
				ft = have[u][i + 1].fi;
			add(0, m, st, ft, val, 1);
			//cout << "OMG " << v << ' ' << u << ' ' << st << ' ' << ft << ' ' << val << endl;
		}
		have[u].clear();
	}
	
	ll me = get(0, m, h[v], 1) + c[v];
	
	//cout << "ajab vaghan " << v << ' ' << h[v] << ' ' << me << endl;
	
	upd(h[v], me);
	
	if(keep) return;
	
	av.clear();
	for(int i = st[v]; i <= ft[v]; i++){
		int u = ver[i];
		av.pb(h[u]);
		if(h[u] + 1 < m) 
			av.pb(h[u] + 1);
	}
	av.pb(0);
	sort(all(av));
	av.resize(unique(all(av)) - av.begin());
	for(auto id : av){
		have[v].pb({id, get(0, m, id, 1)});
	}
	
	while(!ch.empty()){
		int u = ch.back();
		ch.pop_back();
		node[u].clear();
	}
	node[1].clear();
	
	return;
}
 
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n; cin >> n;
	ll sum = 0;
	for(int i = 0; i < n; i++){
		int a; cin >> a >> h[i] >> c[i];
		a--;
		if(i > 0)
			adj[a].pb(i);
		ex.pb(h[i]);
		sum += c[i];
	}
	sort(all(ex));
	ex.resize(unique(all(ex)) - ex.begin());
	for(int i = 0; i < n; i++){
		h[i] = lower_bound(all(ex), h[i]) - ex.begin();
	}
	m = ex.size();
	dfs_det(0);
	dfs(0, true);
	ll ans = get(0, m, 0, 1);
	cout << sum - ans << endl;
}

Compilation message

worst_reporter2.cpp: In function 'void dfs(int, bool)':
worst_reporter2.cpp:145:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |   for(int i = 0; i < have[u].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~
worst_reporter2.cpp:149:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |    if(i + 1 < have[u].size())
      |       ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25380 KB Output is correct
2 Correct 12 ms 25380 KB Output is correct
3 Correct 11 ms 25360 KB Output is correct
4 Correct 12 ms 25376 KB Output is correct
5 Correct 34 ms 28440 KB Output is correct
6 Correct 21 ms 26436 KB Output is correct
7 Correct 16 ms 26032 KB Output is correct
8 Correct 28 ms 27444 KB Output is correct
9 Correct 20 ms 26316 KB Output is correct
10 Correct 19 ms 26024 KB Output is correct
11 Correct 15 ms 25832 KB Output is correct
12 Correct 20 ms 28868 KB Output is correct
13 Correct 16 ms 28000 KB Output is correct
14 Correct 24 ms 27948 KB Output is correct
15 Correct 18 ms 27084 KB Output is correct
16 Correct 34 ms 27568 KB Output is correct
17 Correct 22 ms 26328 KB Output is correct
18 Correct 15 ms 25804 KB Output is correct
19 Correct 24 ms 27908 KB Output is correct
20 Correct 16 ms 27432 KB Output is correct
21 Correct 16 ms 27024 KB Output is correct
22 Correct 17 ms 27076 KB Output is correct
23 Correct 15 ms 26568 KB Output is correct
24 Correct 20 ms 27976 KB Output is correct
25 Correct 17 ms 27440 KB Output is correct
26 Correct 20 ms 28264 KB Output is correct
27 Correct 19 ms 27888 KB Output is correct
28 Correct 20 ms 28100 KB Output is correct
29 Correct 19 ms 28376 KB Output is correct
30 Correct 20 ms 27344 KB Output is correct
31 Correct 20 ms 27304 KB Output is correct

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25380 KB Output is correct
2 Correct 12 ms 25380 KB Output is correct
3 Correct 11 ms 25360 KB Output is correct
4 Correct 12 ms 25376 KB Output is correct
5 Correct 34 ms 28440 KB Output is correct
6 Correct 21 ms 26436 KB Output is correct
7 Correct 16 ms 26032 KB Output is correct
8 Correct 28 ms 27444 KB Output is correct
9 Correct 20 ms 26316 KB Output is correct
10 Correct 19 ms 26024 KB Output is correct
11 Correct 15 ms 25832 KB Output is correct
12 Correct 20 ms 28868 KB Output is correct
13 Correct 16 ms 28000 KB Output is correct
14 Correct 24 ms 27948 KB Output is correct
15 Correct 18 ms 27084 KB Output is correct
16 Correct 34 ms 27568 KB Output is correct
17 Correct 22 ms 26328 KB Output is correct
18 Correct 15 ms 25804 KB Output is correct
19 Correct 24 ms 27908 KB Output is correct
20 Correct 16 ms 27432 KB Output is correct
21 Correct 16 ms 27024 KB Output is correct
22 Correct 17 ms 27076 KB Output is correct
23 Correct 15 ms 26568 KB Output is correct
24 Correct 20 ms 27976 KB Output is correct
25 Correct 17 ms 27440 KB Output is correct
26 Correct 20 ms 28264 KB Output is correct
27 Correct 19 ms 27888 KB Output is correct
28 Correct 20 ms 28100 KB Output is correct
29 Correct 19 ms 28376 KB Output is correct
30 Correct 20 ms 27344 KB Output is correct
31 Correct 20 ms 27304 KB Output is correct
32 Correct 38 ms 27396 KB Output is correct
33 Correct 1357 ms 138172 KB Output is correct
34 Correct 638 ms 64364 KB Output is correct
35 Correct 1409 ms 136248 KB Output is correct
36 Correct 645 ms 64552 KB Output is correct
37 Correct 227 ms 43484 KB Output is correct
38 Correct 192 ms 39184 KB Output is correct
39 Correct 519 ms 176768 KB Output is correct
40 Correct 332 ms 143972 KB Output is correct
41 Correct 149 ms 115184 KB Output is correct
42 Correct 578 ms 147912 KB Output is correct
43 Correct 310 ms 91524 KB Output is correct
44 Correct 1980 ms 152076 KB Output is correct
45 Correct 763 ms 68080 KB Output is correct
46 Correct 111 ms 39328 KB Output is correct
47 Correct 511 ms 142284 KB Output is correct
48 Correct 248 ms 109436 KB Output is correct
49 Correct 145 ms 84668 KB Output is correct
50 Correct 269 ms 108708 KB Output is correct
51 Correct 182 ms 75908 KB Output is correct
52 Correct 510 ms 142716 KB Output is correct
53 Correct 247 ms 109888 KB Output is correct
54 Correct 526 ms 143960 KB Output is correct
55 Correct 397 ms 142632 KB Output is correct
56 Correct 422 ms 159592 KB Output is correct
57 Correct 391 ms 166368 KB Output is correct
58 Correct 586 ms 112200 KB Output is correct
59 Correct 556 ms 112176 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25380 KB Output is correct
2 Correct 12 ms 25380 KB Output is correct
3 Correct 11 ms 25360 KB Output is correct
4 Correct 12 ms 25376 KB Output is correct
5 Correct 34 ms 28440 KB Output is correct
6 Correct 21 ms 26436 KB Output is correct
7 Correct 16 ms 26032 KB Output is correct
8 Correct 28 ms 27444 KB Output is correct
9 Correct 20 ms 26316 KB Output is correct
10 Correct 19 ms 26024 KB Output is correct
11 Correct 15 ms 25832 KB Output is correct
12 Correct 20 ms 28868 KB Output is correct
13 Correct 16 ms 28000 KB Output is correct
14 Correct 24 ms 27948 KB Output is correct
15 Correct 18 ms 27084 KB Output is correct
16 Correct 34 ms 27568 KB Output is correct
17 Correct 22 ms 26328 KB Output is correct
18 Correct 15 ms 25804 KB Output is correct
19 Correct 24 ms 27908 KB Output is correct
20 Correct 16 ms 27432 KB Output is correct
21 Correct 16 ms 27024 KB Output is correct
22 Correct 17 ms 27076 KB Output is correct
23 Correct 15 ms 26568 KB Output is correct
24 Correct 20 ms 27976 KB Output is correct
25 Correct 17 ms 27440 KB Output is correct
26 Correct 20 ms 28264 KB Output is correct
27 Correct 19 ms 27888 KB Output is correct
28 Correct 20 ms 28100 KB Output is correct
29 Correct 19 ms 28376 KB Output is correct
30 Correct 20 ms 27344 KB Output is correct
31 Correct 20 ms 27304 KB Output is correct
32 Correct 38 ms 27396 KB Output is correct
33 Correct 1357 ms 138172 KB Output is correct
34 Correct 638 ms 64364 KB Output is correct
35 Correct 1409 ms 136248 KB Output is correct
36 Correct 645 ms 64552 KB Output is correct
37 Correct 227 ms 43484 KB Output is correct
38 Correct 192 ms 39184 KB Output is correct
39 Correct 519 ms 176768 KB Output is correct
40 Correct 332 ms 143972 KB Output is correct
41 Correct 149 ms 115184 KB Output is correct
42 Correct 578 ms 147912 KB Output is correct
43 Correct 310 ms 91524 KB Output is correct
44 Correct 1980 ms 152076 KB Output is correct
45 Correct 763 ms 68080 KB Output is correct
46 Correct 111 ms 39328 KB Output is correct
47 Correct 511 ms 142284 KB Output is correct
48 Correct 248 ms 109436 KB Output is correct
49 Correct 145 ms 84668 KB Output is correct
50 Correct 269 ms 108708 KB Output is correct
51 Correct 182 ms 75908 KB Output is correct
52 Correct 510 ms 142716 KB Output is correct
53 Correct 247 ms 109888 KB Output is correct
54 Correct 526 ms 143960 KB Output is correct
55 Correct 397 ms 142632 KB Output is correct
56 Correct 422 ms 159592 KB Output is correct
57 Correct 391 ms 166368 KB Output is correct
58 Correct 586 ms 112200 KB Output is correct
59 Correct 556 ms 112176 KB Output is correct
60 Correct 12 ms 25376 KB Output is correct
61 Incorrect 12 ms 25296 KB Output isn't correct
62 Halted 0 ms 0 KB -