Submission #518990

#	Time	Username	Problem	Language	Result	Execution time	Memory
518990		AmShZ	Worst Reporter 4 (JOI21_worst_reporter4)	C++11	100 / 100	1930 ms	78508 KiB

worst_reporter2

//khodaya khodet komak kon
# include <bits/stdc++.h>
#pragma GCC optimize("O2")

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, ll>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 2e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;

int n, a[xn], f[xn], c[xn], sz[xn], hvy[xn], ptr;
ll lazy[xn << 2];
ll sum, ans, seg[xn << 2], cnt[xn], mn[xn << 2], lz[xn << 2];
vector <int> adj[xn], vec, cprs;
vector <ppi> Q[xn];
deque <int> dq;
map <int, int> mp;
bool mark[xn];

void shift(int id, int l, int r){
	seg[id] += lz[id];
	mn[id] += lz[id];
	if (lazy[id] + 1)
		seg[id] = mn[id] = lazy[id];
	if (1 < r - l){
		if (lazy[lc] + 1)
			lazy[lc] += lz[id];
		else
			lz[lc] += lz[id];
		if (lazy[id] + 1)
			lazy[lc] = lazy[id];
		
		if (lazy[rc] + 1)
			lazy[rc] += lz[id];
		else
			lz[rc] += lz[id];
		if (lazy[id] + 1)
			lazy[rc] = lazy[id];
	}
	lazy[id] = - 1;
	lz[id] = 0;
}
void update(int id, int l, int r, int ql, int qr, ll val){
	shift(id, l, r);
	if (qr <= l || r <= ql || qr <= ql || val <= mn[id])
		return;
	if (ql <= l && r <= qr && seg[id] <= val){
		lazy[id] = val;
		shift(id, l, r);
		return;
	}
	int mid = l + r >> 1;
	update(lc, l, mid, ql, qr, val);
	update(rc, mid, r, ql, qr, val);
	seg[id] = max(seg[lc], seg[rc]);
	mn[id] = min(mn[lc], mn[rc]);
}
void upd(int id, int l, int r, int ql, int qr, ll val){
	shift(id, l, r);
	if (qr <= l || r <= ql || qr <= ql)
		return;
	if (ql <= l && r <= qr){
		if (lazy[id] + 1)
			lazy[id] += val;
		else
			lz[id] += val;
		shift(id, l, r);
		return;
	}
	int mid = l + r >> 1;
	upd(lc, l, mid, ql, qr, val);
	upd(rc, mid, r, ql, qr, val);
	seg[id] = max(seg[lc], seg[rc]);
	mn[id] = min(mn[lc], mn[rc]);
}
ll get(int id, int l, int r, int pos){
	shift(id, l, r);
	if (r - l == 1)
		return seg[id];
	int mid = l + r >> 1;
	if (pos < mid)
		return get(lc, l, mid, pos);
	else
		return get(rc, mid, r, pos);
}
void find_cyc(int v){
	dq.push_back(v);
	if (mark[v])
		return;
	mark[v] = true;
	find_cyc(f[v]);
}
void preDFS(int v){
	sz[v] = 1;
	hvy[v] = n + 1;
	for (int u : adj[v]){
		preDFS(u);
		sz[v] += sz[u];
		if (sz[hvy[v]] < sz[u])
			hvy[v] = u;
	}
}
void gooni(int v, bool f = 0){
	if (f)
		mark[v] = true;
	vec.push_back(a[v]);
	for (int u : adj[v])
		gooni(u, f);
}
void DFS(int v){
	Q[v].clear();
	for (int u : adj[v]){
		if (u == hvy[v])
			continue;
		DFS(u);
		vec.clear();
		gooni(u);
		int last = 0;
		sort(all(vec));
		for (int x : vec){
			if (last < x){
				ll y = get(1, 1, ptr + 1, x);
				Q[v].push_back({{last + 1, x}, y});
				last = x;
			}
		}
		lazy[1] = 0;
	}
	if (hvy[v] <= n)
		DFS(hvy[v]);
	for (ppi x : Q[v])
		upd(1, 1, ptr + 1, x.A.A, x.A.B + 1, x.B);
	ll x = get(1, 1, ptr + 1, a[v]) + c[v];
	update(1, 1, ptr + 1, 1, a[v] + 1, x);
}

int main(){
	fast_io;

	cin >> n;
	for (int i = 1; i <= n; ++ i){
		cin >> f[i] >> a[i] >> c[i];
		adj[f[i]].push_back(i);
		cprs.push_back(a[i]);
		sum += c[i];
	}
	sort(all(cprs));
	for (int i = 0; i < SZ(cprs); ++ i)
		if (!i || cprs[i] != cprs[i - 1])
			mp[cprs[i]] = ++ ptr;
	for (int i = 1; i <= n; ++ i)
		a[i] = mp[a[i]];
	fill(lazy, lazy + (xn << 2), - 1);
	for (int i = 1; i <= n; ++ i){
		if (mark[i])
			continue;
		dq.clear();
		find_cyc(i);
		while (dq.front() != dq.back())
			mark[dq.front()] = false, dq.pop_front();
		dq.pop_front();
		adj[0].clear();
		for (int v : dq)
			for (int u : adj[v])
				if (!mark[u])
					adj[0].push_back(u);
		preDFS(0), DFS(0);
		ll mx = get(1, 1, ptr + 1, 1);
		for (int x : dq){
			cnt[a[x]] += c[x];
			mx = max(mx, get(1, 1, ptr + 1, a[x]) + cnt[a[x]]);
		}
		ans += mx;
		for (int x : dq)
			cnt[a[x]] -= c[x];
		vec.clear();
		gooni(0, 1);
		lazy[1] = 0;
	}
	cout << sum - ans << endl;

	return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'void update(int, int, int, int, int, ll)':
worst_reporter2.cpp:78:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |  int mid = l + r >> 1;
      |            ~~^~~
worst_reporter2.cpp: In function 'void upd(int, int, int, int, int, ll)':
worst_reporter2.cpp:96:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |  int mid = l + r >> 1;
      |            ~~^~~
worst_reporter2.cpp: In function 'll get(int, int, int, int)':
worst_reporter2.cpp:106:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |  int mid = l + r >> 1;
      |            ~~^~~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 21 / 21