Submission #1037959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037959		hotboy2703	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	305 ms	127060 KiB

worst_reporter2

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll MAXN = 2e5+100;
const ll INF = 1e18;
ll A[MAXN],H[MAXN],C[MAXN];
ll in[MAXN];
vector <ll> g[MAXN];
map <ll,ll> mp[MAXN];
vector <pll> root[MAXN];
ll re[MAXN];
ll n;	
void dfs(ll u){
	for (auto v:g[u]){
		// cout<<u<<' '<<v<<endl;
		dfs(v);
	}
	for (auto v:g[u]){
		if (sz(mp[v]) > sz(mp[u]))swap(mp[u],mp[v]);
	}
	for (auto v:g[u]){
		for (auto x:mp[v]){
			mp[u][x.fi]+=x.se;
		}
	}
	root[u].push_back(MP(H[u],C[u]));
	map <ll,ll> tmp1;
	for (auto x:root[u])tmp1[x.fi] += x.se;
	for (auto x:tmp1){
		mp[u][-INF]+=x.se;
		auto tmp = mp[u].upper_bound(x.fi);
		ll sum = 0;
		while (sum < x.se){
			tmp = prev(tmp);
			sum += (*tmp).se;
		}
		(*tmp).se -= x.se - (sum - (*tmp).se);
		for (auto it = next(tmp);it != mp[u].end() && (*it).fi <= x.fi;it = mp[u].erase(it)){}
		mp[u][x.fi+1] += x.se;
	}
	// cout<<"MAP "<<u<<endl;
	// for (auto x:mp[u])cout<<x.fi<<' '<<x.se<<endl;
	// cout<<endl;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	cin>>n;
	for (ll i = 1;i <= n;i ++){
		cin>>A[i]>>H[i]>>C[i];
		re[i] = i;
	}
	for (ll i = 1;i <= n;i ++){
		// cout<<i<<endl;
		if (!in[i]){
			ll cur = i;
			vector <ll> all;
			while (!in[cur]){
				all.push_back(cur);
				in[cur] = 1;
				cur = re[A[cur]];
			}
			
			if (in[cur] == 1){
				while (all.back() != cur){
					root[cur].push_back({H[all.back()],C[all.back()]});
					re[all.back()] = cur;
					all.pop_back();
				}
				in[all.back()] = 2;
				for (ll j = sz(all) - 1;j >= 1;j --){
					g[re[all[j]]].push_back(all[j-1]);
				}
			}
			else{
				for (ll j = sz(all) - 1;j >= 1;j --){
					g[re[all[j]]].push_back(all[j-1]);
				}
				g[re[cur]].push_back(all.back());
			}
			for (auto x:all)in[x]++;
			
		}
	}
	// for (ll i = 1;i <= n;i ++){
	// 	for (auto v:g[i])cout<<i<<' '<<v<<endl;
	// }
	ll ans = 0;
	for (ll i = 1;i <= n;i ++){
		// cout<<i<<endl;
		if (in[i] == 3){
			dfs(i);
			ans += (*mp[i].begin()).se;
		}
	}
	cout<<ans;
}

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