Submission #44217

#	Time	Username	Problem	Language	Result	Execution time	Memory
44217		Filyan	Fireworks (APIO16_fireworks)	C++14	100 / 100	733 ms	168124 KiB

fireworks

#include <bits/stdc++.h> 
using namespace std;

#define sz(x) (int)x.size() 
#define pb push_back 
#define mp make_pair 
#define fi(a, b) for(int i=a; i<=b; i++) 
#define fj(a, b) for(int j=a; j<=b; j++) 
#define fo(a, b) for(int o=a; o<=b; o++) 
#define fdi(a, b) for(int i=a; i>=b; i--) 
#define fdj(a, b) for(int j=a; j>=b; j--) 
#define fdo(a, b) for(int o=a; o>=b; o--) 

#ifdef LOCAL
#define err(...) fprintf(stderr, __VA_ARGS__)
#else
#define err(...) while(false) {}
#endif

typedef long long ll; 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<int> vi; 
typedef vector<pii> vpii; 
typedef vector<pll> vpll; 
typedef long double ld;

/////////////////////////////////

int const MAX = 300 * 1000 + 41;

int n, m;
vpii e[MAX];

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

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

	void normalize() {
		while (sz(r) > 1) {
			auto it = r.end();
			it--;
			r.erase(it);		
		}
	}

	ll getleft() {
		auto it = l.end();
		--it;
		ll res = (*it) + addl;
		return res;		
	}

	ll extractleft() {
		ll res = getleft();
		auto it = l.end();
		--it;
		l.erase(it);
		return res;
	}

	ll getright() {
		auto it = r.begin();
		ll res = (*it) + addr;
		return res;		
	}

	ll extractright() {
		ll res = getright();
		auto it = r.begin();
		r.erase(it);
		return res;
	}

	void addedge(int x) {
		addr += x;
		ll y = extractleft();	
		l.insert(y - addl + x);
	}

	void pushl(ll x) {
		l.insert(x - addl);
	}	

	void pushr(ll x) {
		r.insert(x - addr);
	}

};

State st[MAX];

void dfs(int x) {
	if (x >= n + 1) {
		st[x].l.insert(0);
		st[x].r.insert(0);
		return;
	}	
	for (pii z : e[x]) {
		int y = z.first;
		dfs(y);
	}
	ll sum = 0;
	for (pii z : e[x]) {
		int y = z.first;
		int c = z.second;
		sum += st[y].ans;
		st[y].addedge(c);
		st[y].normalize();
	}
	for (pii z : e[x]) {
		int y = z.first;
		if (sz(st[y].l) > sz(st[x].l)) {	
			swap(st[x], st[y]);
		}
	}
	st[x].ans = sum;
	for (pii z : e[x]) {
		int y = z.first;
		while (sz(st[y].l)) {
			ll p = st[y].extractleft();
			if (p <= st[x].getright()) {
				st[x].pushl(p);
			} else {
				st[x].ans += p - st[x].getright();
				st[x].pushl(st[x].extractright());
				st[x].pushr(p);
			}
		}	
		while (sz(st[y].r)) {
			ll p = st[y].extractright();
			if (p >= st[x].getleft()) {
				st[x].pushr(p);
			} else {
				st[x].ans += st[x].getleft() - p;
				st[x].pushr(st[x].extractleft());
				st[x].pushl(p);
			}
		}	
	}
}

void solve() {
	dfs(1);
	printf("%lld\n", st[1].ans);
}

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

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

	
#ifdef LOCAL
	err("ELAPSED TIME: %.3Lf\n", (ld) clock() / CLOCKS_PER_SEC);
#endif	
	
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:161:8: 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