QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#168779 | #6538. Lonely King | PhantomThreshold# | WA | 2ms | 26652kb | C++20 | 2.8kb | 2023-09-08 21:46:22 | 2023-09-08 21:46:23 |
Judging History
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'