Submission #667462

#	Time	Username	Problem	Language	Result	Execution time	Memory
667462		Arsa	Fireworks (APIO16_fireworks)	C++17	7 / 100	4 ms	7372 KiB

fireworks

#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

const int N = 3e5+10;
const ll INF = 1e16;

ll n,m;
vector <pll> G[N];
ll ps[N];
ll Ans;

void Input();
ll Dfs(int);

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	Input();
	ll d = Dfs(0);
	cout << Ans << endl;
}

void Input(){
	cin >> n >> m;
	for(int i = 1;i < n+m;i++){
		int p,w;
		cin >> p >> w, p--;
		G[p].push_back({i, w});
	}
}

ll Dfs(int v){
	if(G[v].size() == 0)
		return 0;
		
	ll mx = 0;
	vector <ll> vec;
	for(int i = 0;i < G[v].size();i++){
		int u = G[v][i].F;
		ll res = Dfs(u);
		mx = max(mx, res), vec.push_back(res + G[v][i].S);
	}
	
	sort(vec.begin(), vec.end());
	ps[0] = vec[0];
	for(int i = 1;i < vec.size();i++)
		ps[i] = ps[i-1] + vec[i];
		
	ll sum = 0, ans = INF, dis = 0;
	for(ll i = vec.size()-1;0 <= i;i--){
		ll x = vec[i];
		if(x < mx)
			break;
		if((x * (i+1) - ps[i]) + sum - (x * (vec.size() - (i+1))) <= ans)
			ans = (x * (i+1) - ps[i]) + sum - (x * (vec.size() - (i+1))) , dis = x;
		sum += x;
	}
	
	Ans += ans;
	//cout << "v=" << v << " ans=" << ans <<" dis="<<dis<< endl;
	return dis;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:23:5: warning: unused variable 'd' [-Wunused-variable]
   23 |  ll d = Dfs(0);
      |     ^
fireworks.cpp: In function 'll Dfs(int)':
fireworks.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i = 0;i < G[v].size();i++){
      |                ~~^~~~~~~~~~~~~
fireworks.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i = 1;i < vec.size();i++)
      |                ~~^~~~~~~~~~~~
fireworks.cpp:58:61: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   58 |   if((x * (i+1) - ps[i]) + sum - (x * (vec.size() - (i+1))) <= ans)
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

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