Submission #39361

#	Time	Username	Problem	Language	Result	Execution time	Memory
39361		Filyan	Fireworks (APIO16_fireworks)	C++14	100 / 100	759 ms	137812 KiB

fireworks

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

#define sz(x) (int)(x.size())
#define fi(a,b) for(int i=a;i<b;++i)
#define fj(a,b) for(int j=a;j<b;++j)
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
/////////////////////////

int const N = 3e5 + 41;

int n, m;
vector<pii> e[N];
ll ans;

struct Fun{
	multiset<ll> l, r;
	ll addl, addr;
	ll ans;

	Fun(){
		addl = addr = ans = 0;
	};

	Fun(int c){
		addl = addr = ans = 0;
		l.insert(c);
		r.insert(c);
	}

	int getq(){
		return sz(l) + sz(r);
	}

	ll getleftmostmin(){
		ll x = (*l.rbegin());
		return x + addl;
	}

	ll getrightmostmin(){
		ll x = (*r.begin());
		return x + addr;
	}

	ll extractleftmostmin(){
		ll x = (*l.rbegin());
		l.erase(l.find(x));
		return x + addl;
	}

	ll extractrightmostmin(){
		ll x = (*r.begin());
		r.erase(r.begin());
		return x + addr;
	}

	void pushrightpoint(ll x){
		if(x >= getleftmostmin()){
			r.insert(x - addr);
		}else{
			ll lx = extractleftmostmin();
			ans += lx - x;
			l.insert(x - addl);
			r.insert(lx - addr);
		}
	}

	void pushright(multiset<ll> &rp, ll addright){
		for(ll x : rp){
			pushrightpoint(x + addright);
		}
	}

	void pushleftpoint(ll x){
		if(x <= getrightmostmin()){
			l.insert(x - addl);
		}else{
			ll rx = extractrightmostmin();
			ans += x - rx;
			l.insert(rx - addl);
			r.insert(x - addr);
		}
	}

	void pushleft(multiset<ll> &lp, ll addleft){
		for(ll x : lp){
			pushleftpoint(x + addleft);
		}
	}

	void shift(ll s){
		addr += s;
		addl += s;
		ll lx = extractleftmostmin();
		addl -= s;
		l.insert(lx - addl);
	}

	void relax(){
		while(sz(r) > 1){
			ll x = (*r.rbegin());
			r.erase(r.find(x));
		}
	}
};

Fun *f[N];

void dfs(int x, int p = -1, int c = 0){
	if(x >= n){
		f[x] = new Fun(c);
		return;
	}
	f[x] = new Fun();
	int id = x;
	for(pii e : ::e[x]){
		int y = e.first;
		if(y == p) continue;
		int c = e.second;
		dfs(y, x, c);
		if(f[x]->getq() < f[y]->getq()){
			f[x] = f[y];
			id = y;
		}
	}
	for(pii e : ::e[x]){
		int y = e.first;
		int c = e.second;
		if(y == id) continue;
		if(y == p) continue;
		f[x]->ans += f[y]->ans;
		f[x]->pushleft(f[y]->l, f[y]->addl);
		f[x]->pushright(f[y]->r, f[y]->addr);
	}

	if(p != -1){
		f[x]->shift(c);
		f[x]->relax();
	}
	//cerr << x << " " << f[x]->ans << endl;
}

void solve(){
	fi(0, n) f[i] = new Fun();
	dfs(0);
	ans = f[0]->ans;
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

	scanf("%d %d",&n,&m);
	fi(1, n+m){
		int p, c;
		scanf("%d %d",&p,&c);
		--p;
		e[p].pb(mp(i, c));
		e[i].pb(mp(p, c));
	}

	solve();

	printf("%lld\n",ans);

	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int, int, int)':
fireworks.cpp:135:7: warning: unused variable 'c' [-Wunused-variable]
   int c = e.second;
       ^
fireworks.cpp: In function 'int main()':
fireworks.cpp:162:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
fireworks.cpp:165:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&p,&c);
                       ^

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45