oj.uz

답안 #834128

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834128 2023-08-22T11:00:22 Z MODDI Fireworks (APIO16_fireworks) C++14
0 / 100
 7 ms 14292 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 7 ms 14292 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 7 ms 14292 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 7 ms 14292 KB Output isn't correct
3 Halted 0 ms 0 KB -