Submission #1198308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198308		ansori	Tree (IOI24_tree)	C++20	38 / 100	2100 ms	248624 KiB

tree

#include "tree.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second 
using namespace std;
const ll N = 2e5 + 52;
bool chk , oko;
ll n;
ll ans , sml;
vector<int> p , w;
vector<ll> g[N];
priority_queue<pair<ll , ll>> st[N];
ll in[N] , out[N] , tim;
set<ll> stp;
class segtree {
public :
	ll sz;
	ll kur;
	vector<ll> t;
	segtree (ll n) : sz(n * 2) , kur(0) , t(vector<ll> (n * 4 , 0)) { }
	
	void update (ll v, ll l, ll r, ll j , ll x) {
		if(r - l == 1 and l == j) t[v] = x;
		else {
			ll m = (l + r) / 2;
			if(j < m) update (v * 2 , l, m, j , x);
			else update (v * 2 + 1 , m , r , j , x);
			t[v] = t[v * 2] + t[v * 2 + 1];
		}
	}
	void gett(ll v, ll l, ll r , ll l1 , ll r1) {
	    if(l <= l1 and r >= r1) kur += t[v];
	    else {
	       	ll m = (l1 + r1) / 2;
	       	if(!(l1 >= r || m <= l)) {
	            gett(v * 2 , l , r , l1 , m);
	    	}
	    	if(!(m >= r || r1 <= l)) {
	    	   	gett(v * 2 + 1 , l , r , m , r1);
	    	}
	    }
	}
	void upd(ll p , ll x){
		update(1 , 0 , sz , p , x);	
	}
	ll get(ll l , ll r){
		kur = 0;
		gett(1 , l , r + 1 , 0 , sz);
		return kur;
	}
};
ll l , r;
void dfs(ll v , segtree & t){
	for(auto to : g[v]){
		dfs(to , t);
	}
	ll u = v;
	for(auto to : g[v]){
		if(oko) continue ;
		if(st[to].size() > st[v].size()){
			swap(st[v] , st[to]);
		}
		while(st[to].size()){
			st[v].push(st[to].top());
			st[to].pop();
		}
	}	
	st[v].push({-w[v] , v});
	t.upd(in[v] , 0);
	if(g[v].size() == 0){
		t.upd(in[v] , l);
		stp.erase(in[v]);
		return ;
	}
	if(oko){
		ll val = max(0ll , t.get(in[v] , out[v]) - r);
		ans += w[v] * val;
		t.upd(in[v] , -val);
		return ;
	}
	while(t.get(in[v] , out[v]) > r){
		auto u = st[v].top().se;
		auto ww = st[v].top().fi;
		st[v].pop();
		if(stp.find(in[u]) == stp.end()){
			continue ;
		}
		//cout << u << ' ' << ww << '\n';
		ll val = min(t.get(in[u] , out[u]) - l , t.get(in[v] , out[v]) - r);
		//cout << val << ' ';
		ans += val * (-ww);
		t.upd(in[u] , t.get(in[u] , in[u]) - val);
		//cout << t.get(in[u] , out[u]) << ' ';
		if(t.get(in[u] , out[u]) == l){
			while(stp.lower_bound(in[u]) != stp.end() and (*stp.lower_bound(in[u])) <= out[u]){
				stp.erase(stp.lower_bound(in[u]));
			}
		}
		else st[v].push({ww , u});
	}
	//cout << v << ' ' << ans << '\n';
}
void dffs(ll v){
	in[v] = (++ tim);
	for(auto to : g[v]){
		dffs(to);
	}
	out[v] = tim;
}
void init(std::vector<int> P, std::vector<int> W) {
	p = P , w = W;
	n = p.size();
	chk = 1;
	bool oko = true;
	for(ll i = 0;i < n; ++ i){
		if(w[i] != 1) chk = false;
		if(i) g[p[i]].push_back(i);
		if(w[i] < w[p[i]]) oko = false;
	}
	for(ll i = 0;i < n; ++ i){
		if(g[i].size() == 0){
			sml += w[i];
		}
	}
	tim = -1;
	dffs(0);
}

long long query(int L, int R) {
	ans = 0;
	l = L;
	r = R;
	if(! chk){
		ans += L * sml;
		while(st[0].size()) st[0].pop();
		for(ll i = 0;i < n; ++ i) stp.insert(i);
		segtree t(n);
		dfs(0 , t);
	}
	else{
		//cout << sml << ' ';
		ans = L * sml + max(0ll , L * sml - R);
	}
  	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 7 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19