Submission #519548

#	Time	Username	Problem	Language	Result	Execution time	Memory
519548		fatemetmhr	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	1939 ms	181496 KiB

worst_reporter2

//  ~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 = 0;
	for(int i = 0; i < m; i++)
		ans = max(ans, get(0, m, i, 1));
	cout << sum - ans << endl;
}

Compilation message (stderr)

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 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21