oj.uz

Submission #211790

# Submission time Handle Problem Language Result Execution time Memory
211790 2020-03-21T09:32:45 Z kig9981 Fireworks (APIO16_fireworks) C++17
7 / 100
 13 ms 14464 KB 
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

vector<pair<int,int>> adj[300000];
int parent[300000];
vector<pair<long long,long long>> D[300000];

void dfs(int c)
{
	vector<long long> x(1);
	vector<pair<long long,long long>> C;
	long long A=0, B=0, A0, B0, A1, B1;
	if(adj[c].empty()) {
		D[c].emplace_back(0,0);
		return;
	}
	for(auto[n,w]: adj[c]) {
		dfs(n);
		if(D[n].size()>1 && D[n][D[n].size()-2].second==D[n][D[n].size()-1].second) {
			D[n].push_back(D[n].back());
			D[n][D[n].size()-2]=D[n][D[n].size()-3];
			x.push_back(D[n][D[n].size()-1].first+=w);
			x.push_back(D[n][D[n].size()-2].first+=w);
			for(int i=0;i<D[n].size()-2;i++) {
				D[n][i].second+=w;
				x.push_back(D[n][i].first);
			}
		}
		else if(D[n].size()>1) {
			x.push_back(D[n].back().first+=w);
			for(int i=0;i<(int)D[n].size()-1;i++) {
				D[n][i].second+=w;
				x.push_back(D[n][i].first);
			}
		}
		else {
			D[n].emplace_back(w,0);
			D[n][0].second=w;
			x.push_back(w);
		}
	}
	sort(x.begin(),x.end());
	x.resize(unique(x.begin(),x.end())-x.begin());
	C.resize(x.size());
	for(auto[n,w]: adj[c]) {
		if(D[n].size()>1) {
			A+=(D[n][1].second-D[n][0].second)/D[n][1].first;
			B+=D[n][0].second;
		}
		else {
			A++;
			B+=D[n][0].second;
		}
		for(int i=1;i<D[n].size();i++) {
			int p=lower_bound(x.begin(),x.end(),D[n][i].first)-x.begin();
			A0=(D[n][i].second-D[n][i-1].second)/(D[n][i].first-D[n][i-1].first);
			B0=-A0*D[n][i].first+D[n][i].second;
			if(i+1==D[n].size()) A1=1;
			else A1=(D[n][i].second-D[n][i+1].second)/(D[n][i].first-D[n][i+1].first);
			B1=-A1*D[n][i].first+D[n][i].second;
			C[p].first+=A1-A0;
			C[p].second+=B1-B0;
		}
	}
	D[c].emplace_back(0,B);
	for(int i=1;i<x.size();i++) {
		A+=C[i].first; B+=C[i].second;
		if(A*x[i]+B<=D[c].back().second) D[c].emplace_back(x[i],A*x[i]+B);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M;
	cin>>N>>M; N+=M;
	for(int i=1;i<N;i++) {
		int c;
		cin>>parent[i]>>c;
		adj[--parent[i]].emplace_back(i,c);
	}
	dfs(0);
	cout<<D[0].back().second<<'\n';
	return 0;
}

Compilation message

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<D[n].size()-2;i++) {
                ~^~~~~~~~~~~~~~
fireworks.cpp:63:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<D[n].size();i++) {
               ~^~~~~~~~~~~~
fireworks.cpp:67:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i+1==D[n].size()) A1=1;
       ~~~^~~~~~~~~~~~~
fireworks.cpp:54:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) {
              ^
fireworks.cpp:75:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<x.size();i++) {
              ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 13 ms 14464 KB Output is correct
3 Correct 13 ms 14464 KB Output is correct
4 Correct 12 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 12 ms 14464 KB Output is correct
7 Correct 13 ms 14464 KB Output is correct
8 Correct 12 ms 14464 KB Output is correct
9 Correct 12 ms 14464 KB Output is correct
10 Correct 12 ms 14464 KB Output is correct

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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