QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168779#6538. Lonely KingPhantomThreshold#WA 2ms26652kbC++202.8kb2023-09-08 21:46:222023-09-08 21:46:23

Judging History

你现在查看的是最新测评结果

  • [2023-09-08 21:46:23]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:26652kb
  • [2023-09-08 21:46:22]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int maxn = 210000;

int n;
vector<int>V[maxn];

//        k   c
set< pair<int,int> >S[maxn]; int flag[maxn];

int s[maxn],siz[maxn];
int g[maxn];

long double intersect( const pair<int,int>k1, const pair<int,int>k2 )
{
	return (long double)(k2.second-k1.second)/(k1.first-k2.first);
}
void add(set< pair<int,int> >&SS, const pair<int,int>x)
{
	auto qx= make_pair(x.first,0);
	
	auto it= SS.lower_bound(qx);
	if(it->first==x.first)
	{
		if(it->second<=x.second) return;
		else
		{
			SS.erase(it);
			it= SS.lower_bound(qx);
		}
	}
	long double l=-1, r=1e8;
	
	auto itr= it;
	if(itr!=SS.begin())
	{
		itr--;
		while(1)
		{
			r= intersect( x,*itr );
			
			if(itr!=SS.begin())
			{
				auto itrr= itr; itrr--;
				auto tempr= intersect( *itr,*itrr );
				if( r>tempr )
				{
					SS.erase(itr);
					itr=itrr;
					continue;
				}
			}
			break;
		}
	}
	auto itl= it;
	if(itl!=SS.end())
	{
		while(1)
		{
			l= intersect( x,*itl );
			
			auto itll= itl; itll++;
			if(itll!=SS.end())
			{
				auto templ= intersect( *itl, *itll );
				if(templ>l)
				{
					SS.erase(itl);
					itl=itll;
					continue;
				}
			}
			break;
		}
	}
	
	if(l>r) return;
	SS.insert( x );
}
int query(set< pair<int,int> >&SS,const int ff,const int x)
{
	int ret=LLONG_MAX;
	int l=1,r=1e6;
	while(l<=r)
	{
		const int mid= (l+r)>>1;
		auto it= SS.lower_bound( make_pair(mid,0) );
		if(it==SS.end()) r=mid-1;
		else
		{
			ret=min(ret, it->first * x + it->second + ff);
			
			auto itl=it; itl++;
			long double loc=-1;
			if(itl!=SS.end()) loc=intersect(*itl, *it);
			
			if(loc<x) r=mid-1;
			else l=mid+1;
		}
	}
	return ret;
}
void merge(int x,int y)
{
	if(S[x].size()<S[y].size())
	{
		swap(S[x],S[y]);
		swap(flag[x],flag[y]);
	}
	for(auto it:S[y])
	{
		it.second+= flag[y]-flag[x];
		add(S[x],it);
	}
}
int ug[maxn];
void dp(const int x)
{
	int sumg=0;
	siz[x]=s[x];
	if(V[x].size()>0)
	{
		for(auto y:V[x]) 
		{
			dp(y);
			siz[x]+=siz[y];
			sumg+=g[y];
		}
		
		g[x]=0;
		for(auto y:V[x])
		{
			ug[y]= query(S[y],flag[y],s[x]);
			g[x]+=ug[y];
			
	//		int adc= sumg-g[y]+(siz[x]-s[x])*s[x]-s[x]*siz[y];
	//		flag[y]+=adc;
			
	//		merge(x,y);
		}
		for(auto y:V[x])
		{
			int adc= g[x]-ug[y]+ query(S[y],flag[y],0);
			flag[y]+=adc;
			
			merge(x,y);
		}
		
	//	g[x]=query(S[x],flag[x],s[x]);
	}
	else
	{
		g[x]=0;
		flag[x]=0;
		add(S[x],make_pair(s[x],0));
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		int x; cin>>x;
		V[x].push_back(i);
	}
	for(int i=1;i<=n;i++) cin>>s[i];
	
	dp(1);
	cout<<g[1]<<endl;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 24916kb

input:

4
1 1 2
2 1 3 2

output:

10

result:

ok 1 number(s): "10"

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 26652kb

input:

50
1 2 1 1 2 1 6 3 7 5 11 11 8 10 7 8 9 7 17 2 18 4 23 8 17 21 3 19 2 4 21 18 1 26 21 36 26 24 7 7 29 27 19 29 36 11 29 42 21
15 31 15 40 15 33 2 33 15 6 50 48 33 6 43 36 19 37 28 32 47 50 8 26 50 44 50 31 32 44 22 15 46 11 33 38 22 27 43 29 8 1 21 31 28 26 39 29 39 42

output:

31403

result:

wrong answer 1st numbers differ - expected: '22728', found: '31403'