oj.uz

답안 #211791

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -