oj.uz

Submission #667462

# Submission time Handle Problem Language Result Execution time Memory
667462 2022-12-01T12:07:18 Z Arsa Fireworks (APIO16_fireworks) C++17
7 / 100
 4 ms 7372 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 3 ms 7252 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7368 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 3 ms 7252 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7368 KB Output is correct
11 Incorrect 4 ms 7252 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 3 ms 7252 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7368 KB Output is correct
11 Incorrect 4 ms 7252 KB Output isn't correct
12 Halted 0 ms 0 KB -