oj.uz

Submission #211791

# Submission time Handle Problem Language Result Execution time Memory
211791 2020-03-21T09:34:25 Z kig9981 Fireworks (APIO16_fireworks) C++17
7 / 100
 14 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) {
			D[n].push_back(D[n].back());
			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:64:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<D[n].size();i++) {
               ~^~~~~~~~~~~~
fireworks.cpp:68:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i+1==D[n].size()) A1=1;
       ~~~^~~~~~~~~~~~~
fireworks.cpp:55:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) {
              ^
fireworks.cpp:76: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 13 ms 14464 KB Output is correct
5 Correct 12 ms 14464 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Correct 12 ms 14464 KB Output is correct
8 Correct 13 ms 14464 KB Output is correct
9 Correct 13 ms 14464 KB Output is correct
10 Correct 13 ms 14464 KB Output is correct

Subtask #2
0 / 19.0

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