oj.uz

Submission #793179

# Submission time Handle Problem Language Result Execution time Memory
793179 2023-07-25T15:16:14 Z algorithm16 Fireworks (APIO16_fireworks) C++14
7 / 100
 4 ms 7376 KB 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int llint;
vector <pair<int,int> > v[300005];
vector <llint> v1,sum;
pair <llint,llint> dp[300005];
llint calc(llint l) {
	if(v1.empty()) return 0;
	llint idx=lower_bound(v1.begin(),v1.end(),l+1)-v1.begin();
	llint ret=idx*l-(v1.size()-idx)*l;
	ret+=sum[v1.size()-1];
	if(idx) ret-=2*sum[idx-1];
	return ret;
}
llint find_l() {
	if(v1.empty()) return 0;
	llint lo=0,hi=1e18;
	while(lo<hi) {
		llint mid=(lo+hi)/2;
		if(calc(mid)<calc(mid+1)) hi=mid;
		else lo=mid+1;
	}
	return lo;
}
void rec(int x) {
	llint ret=0,l=0;
	v1.clear();
	sum.clear();
	for(int i=0;i<v[x].size();i++) {
		rec(v[x][i].first);
	}
	for(int i=0;i<v[x].size();i++) {
		ret+=dp[v[x][i].first].first;
		v1.push_back(v[x][i].second+dp[v[x][i].first].second);
	}
	sort(v1.begin(),v1.end());
	llint sum1=0;
	for(int i=0;i<v1.size();i++) {
		sum1+=v1[i];
		sum.push_back(sum1);
	}
	l=find_l();
	ret+=calc(l);
	dp[x]=make_pair(ret,l);
	//cout << x << "  " << ret << " " << l << "\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<n+m;i++) {
		int x,c;
		cin >> x >> c;
		v[x-1].push_back(make_pair(i,c));
	}
	rec(0);
	cout << dp[0].first;
	return 0;
}

Compilation message

fireworks.cpp: In function 'void rec(int)':
fireworks.cpp:31:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i=0;i<v[x].size();i++) {
      |              ~^~~~~~~~~~~~
fireworks.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0;i<v[x].size();i++) {
      |              ~^~~~~~~~~~~~
fireworks.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0;i<v1.size();i++) {
      |              ~^~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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