QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#407382 | #6538. Lonely King | xuqin | ML | 1ms | 7916kb | C++14 | 5.0kb | 2024-05-08 17:09:30 | 2024-05-08 17:09:44 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
#include<set>
#include<random>
#include<chrono>
#include<bitset>
#include<map>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#define eb emplace_back
using namespace std;
const int maxn=2e5+10, maxm=11+10, inf=2e9+10, P=1e9+7;
const double eps=1e-10, pi=acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
const LL INF=4e18;
typedef pair<LL, int> pli;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
inline int read() {
int x=0, f=1; char c=getchar();
for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=0;
for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
return f?x:-x;
}
mt19937 rnd((unsigned)chrono::steady_clock::now().time_since_epoch().count());
inline int ksm(int x, int y) {
int s=1;
for(; y; y>>=1, x=1LL*x*x%P)
if(y&1) s=1LL*s*x%P;
return s;
}
inline int add(int x, int y) {x+=y; return x>=P?x-P:x;}
inline int del(int x, int y) {x-=y; return x<0?x+P:x;}
LL gcd(LL x, LL y) {return y?gcd(y, x%y):x;}
struct pj{
int lc, rc, sz; LL ad;
LL x, y;
} tr[maxn]; int cnt;
inline void update(int u) {
tr[u].lc=tr[tr[u].lc].sz+tr[tr[u].rc].sz+1;
}
inline int cmp(int x, int y) { //key(x)>key(y)
return rnd()%(tr[x].sz+tr[y].sz)<tr[x].sz;
}
inline int add_n(LL x, LL y) {
int u=++cnt;
tr[u].x=x; tr[u].y=y; tr[u].sz=1;
return u;
}
inline void pushdown(int u) {
if(tr[u].ad==0) return;
if(tr[u].lc) tr[tr[u].lc].y+=tr[u].ad, tr[tr[u].lc].ad+=tr[u].ad;
if(tr[u].rc) tr[tr[u].rc].y+=tr[u].ad, tr[tr[u].rc].ad+=tr[u].ad;
tr[u].ad=0;
}
void splitrk(int u, int rk, int& x, int& y) {//x:<=rk y:>rk
if(u==0) {x=y=0; return;}
pushdown(u);
if(tr[tr[u].lc].sz+1<=rk) {
x=u; splitrk(tr[u].rc, rk-(tr[tr[u].lc].sz+1), tr[x].rc, y);
update(x);
} else {
y=u; splitrk(tr[u].lc, rk, x, tr[y].lc);
update(y);
}
}
void splitval(int u, LL val, int& x, int& y) {//x:<=val y:>val
if(u==0) {x=y=0; return;}
pushdown(u);
if(tr[u].x<=val) {
x=u; splitval(tr[u].rc, val, tr[x].rc, y);
update(x);
} else {
y=u; splitval(tr[u].lc, val, x, tr[y].lc);
update(y);
}
}
int merge(int x, int y) {
if(x==0||y==0) return x^y;
int u;
pushdown(x); pushdown(y);
if(cmp(x, y)) u=x, tr[u].rc=merge(tr[x].rc, y);
else u=y, tr[u].lc=merge(x, tr[y].lc);
update(u);
return u;
}
struct tg{int y, nxt;} g[maxn];
int len, la[maxn];
inline void add_e(int x, int y) {g[++len].y=y; g[len].nxt=la[x]; la[x]=len;}
LL f[maxn], c[maxn];
int rt[maxn], sz[maxn], lst[maxn], tot;
void getlst(int x) {
pushdown(x);
if(tr[x].lc) getlst(tr[x].lc);
lst[++tot]=x;
if(tr[x].rc) getlst(tr[x].rc);
}
inline int cmpslope(LL x, LL y, LL z, LL w) {
//x/y>=z/w
return (__int128)x*w>=(__int128)y*z;
}
inline void inspoint(int nw, int oth) {
tot=0;
getlst(oth);
for(int t=1; t<=tot; ++t) {
LL x=tr[lst[t]].x, y=tr[lst[t]].y;
int u, v, w, p;
splitval(nw, x, w, v);
splitval(w, x-1, u, p);
if(p!=0) {
if(y<tr[p].y) tr[p].y=y;
continue;
}
if(u==0||v==0) {nw=merge(merge(u, add_n(x, y)), v); continue;}
int l, lp;
splitrk(u, tr[u].sz-1, l, lp);
int rp, r;
splitrk(v, 1, rp, r);
if(cmpslope(y-tr[lp].y, x-tr[lp].x, tr[rp].y-tr[lp].y, tr[rp].x-tr[lp].x)) continue;
while(l) {
int nl, np;
splitrk(l, tr[l].sz-1, nl, np);
if(cmpslope(tr[lp].y-tr[np].y, tr[lp].x-tr[np].x, y-tr[np].y, x-tr[np].x)) {
l=nl; lp=np;
} else break;
}
while(r) {
int nr, np;
splitrk(r, 1, np, nr);
if(cmpslope(tr[np].y-y, tr[np].x-x, tr[np].y-tr[rp].y, tr[np].x-tr[rp].x)) {
r=nr; lp=np;
} else break;
}
nw=merge(merge(merge(l, lp), add_n(x, y)), merge(rp, r));
}
}
void dfs(int x, int F) {
sz[x]=1;
if(la[x]==0) {
f[x]=c[F]*c[x];
rt[x]=add_n(c[x], 0);
return;
}
LL sum=0; int p=0;
for(int i=la[x]; i; i=g[i].nxt) {
int y=g[i].y;
dfs(y, x);
sum+=f[y]; sz[x]+=sz[y];
if(sz[y]>sz[p]) p=y;
}
rt[x]=rt[p]; tr[rt[x]].ad+=sum-f[p];
for(int i=la[x]; i; i=g[i].nxt) {
int y=g[i].y;
if(y!=p) tr[rt[y]].ad+=sum-f[y], inspoint(rt[x], rt[y]);
}
//calc f
//k=-c[F]
int u=rt[x];
pll lb=make_pair(-1, -1), rb=make_pair(-1, -1);
f[x]=INF;
while(1) {
//getnxt
f[x]=min(f[x], tr[u].y+tr[u].x*c[F]);
pll nxt;
if(tr[u].rc) {
int t=tr[u].rc;
while(tr[t].lc) t=tr[t].lc;
nxt=make_pair(tr[t].x, tr[t].y);
} else nxt=rb;
if(nxt.first==-1) {
if(tr[u].lc==0) break;
rb=make_pair(tr[u].x, tr[u].y);
u=tr[u].lc;
} else {
if(cmpslope(nxt.second-tr[u].y, nxt.first-tr[u].x, -c[F], 1)) {
if(tr[u].lc==0) break;
rb=make_pair(tr[u].x, tr[u].y);
u=tr[u].lc;
} else {
lb=make_pair(tr[u].x, tr[u].y);
u=tr[u].rc;
}
}
}
}
int main() {
int n=read();
for(int i=2, x; i<=n; ++i) {
x=read(); add_e(x, i);
}
for(int i=1; i<=n; ++i) c[i]=read();
LL prt=0;
for(int i=la[1]; i; i=g[i].nxt) {
int y=g[i].y;
dfs(y, 1);
prt+=f[y];
}
printf("%lld", prt);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7916kb
input:
4 1 1 2 2 1 3 2
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: -100
Memory Limit Exceeded
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