Submission #834128

#	Time	Username	Problem	Language	Result	Execution time	Memory
834128		MODDI	Fireworks (APIO16_fireworks)	C++14	0 / 100	7 ms	14292 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m;
vector<pair<int, ll> > G[300100];
vector<pll> active[300100];
void dfs(int node, int p){
//	cout<<node<<endl;
//	vi children;
	for(auto next : G[node]){
		if(next.first != p){
			dfs(next.first, node);
			for(auto t : active[next.first]){
				active[node].pb(mp(t.first + next.second, t.second));
			}
		}
	}
	if(active[node].size() == 0){
		active[node].pb(mp(0, 0));
		return;
	}
//	cout<<node<<" "<<active[node].size()<<endl;
	sort(active[node].begin(), active[node].end());
	ll eden = 0, dva = 0;
	int mid = ((int)active[node].size()-1)/2;
//	cout<<"Choosed AT: "<<node<<" "<<active[node][mid].first<<" "<<active[node][mid].second<<endl;
	ll wei1 = active[node][mid].first, wei2 = 0;
	for(auto t : active[node]){
		eden += t.second + abs(t.first - wei1);
//		cout<<"FROM "<<t.first<<" to "<<wei1<<endl;
	}
//	cout<<"ONLY USED: "<<eden<<endl;
	mid++;
	if(active[node].size()%2 == 0){
		wei2 = active[node][mid].first;
		for(auto t : active[node]){
			dva += t.second + abs(t.first - active[node][mid].first);
		}
	}
	active[node].clear();
//	active[node].pb(mp(wei1, eden));
	if(dva != 0 && wei2 != 0){
		if(eden > dva)
			active[node].pb(mp(wei2, dva));
		else 
			active[node].pb(mp(wei1, eden));
	}
	else
		active[node].pb(mp(wei1, eden));
}
int main(){
	cin>>n>>m;
	vector<array<int, 3>> edge;
	for(int i = 1; i < n + m; i++){
		int a, b;
		cin>>a>>b;
		a--;
		edge.pb({i, a, b});
		G[a].pb(mp(i, b));
		G[i].pb(mp(a, b));
	}
//	cout<<endl;
	dfs(0, -1);
	ll ans = 1e9;
	for(auto t : active[0]){
		ans = min(ans, t.second);
	}
	cout<<ans<<endl;
	return 0;
}

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