QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#407507#6538. Lonely KingxuqinWA 68ms24180kbC++145.8kb2024-05-08 20:41:272024-05-08 20:41:27

Judging History

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

  • [2024-05-08 20:41:27]
  • 评测
  • 测评结果:WA
  • 用时:68ms
  • 内存:24180kb
  • [2024-05-08 20:41:27]
  • 提交

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].sz=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) {
//	assert(x>0);
	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;
}
void print(int u) {
	printf("%d:lc=%d rc=%d (%lld, %lld)\n", u, tr[u].lc, tr[u].rc, tr[u].x, tr[u].y);
	pushdown(u);
	if(tr[u].lc) print(tr[u].lc);
	if(tr[u].rc) print(tr[u].rc);
}
inline void inspoint(int& nw, int oth) {
	tot=0;
	//puts("in");
	getlst(oth);
	for(int t=1; t<=tot; ++t) {
		LL x=tr[lst[t]].x, y=tr[lst[t]].y;
		tr[lst[t]].lc=tr[lst[t]].rc=0;
	//	printf("ins (%lld, %lld)\n", x, 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;
			nw=merge(merge(u, p), v);
			continue;
		}
		int l=0, lp=0, rp=0, r=0;
	//	printf("u=%d v=%d\n", u, v);
		if(u) splitrk(u, tr[u].sz-1, l, lp);
		if(v) splitrk(v, 1, rp, r);
		//printf("l=%d lp=%d rp=%d r=%d\n", l, lp, rp, r);
		if(lp&&rp) 
			if(cmpslope(y-tr[lp].y, x-tr[lp].x, tr[rp].y-tr[lp].y, tr[rp].x-tr[lp].x)) {
				nw=merge(merge(l, lp), merge(rp, r));
				continue;
			}
	//	printf("l=%d lp=%d rp=%d r=%d\n", l, lp, rp, r);
		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;
			//	printf("del\n");
			} else {l=merge(nl, np); 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; rp=np;
			} else {r=merge(np, nr); break;}
		}
		nw=merge(merge(merge(l, lp), lst[t]), merge(rp, r));
	//printf("nw=%d\n", nw);
	//print(nw);
	}
	//puts("out");
}

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]; tr[rt[x]].y+=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], tr[rt[y]].y+=sum-f[y], inspoint(rt[x], rt[y]);
	}
	//calc f
	//k=-c[F]
	int u=rt[x];
	pll rb=make_pair(-1, -1);
	f[x]=INF;
	while(1) {
		//getnxt
		//printf(" u=%d\n", u);
		f[x]=min(f[x], tr[u].y+tr[u].x*c[F]);
		pushdown(u);
		pll nxt;
		if(tr[u].rc) {
			int t=tr[u].rc;
			while(tr[t].lc) pushdown(t), 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 {
				if(tr[u].rc==0) break;
				u=tr[u].rc;
			}
		}
	}
}
int main() {
//	freopen("3.in", "r", stdin);
	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];
	}
//	for(int i=2; i<=n; ++i) printf("f[%d]=%lld\n", i, f[i]);
	printf("%lld", prt);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7976kb

input:

4
1 1 2
2 1 3 2

output:

10

result:

ok 1 number(s): "10"

Test #2:

score: 0
Accepted
time: 0ms
memory: 5724kb

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:

22728

result:

ok 1 number(s): "22728"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5940kb

input:

500
1 1 2 4 3 1 7 2 8 10 8 12 1 7 11 9 14 18 1 17 9 1 16 17 6 14 17 1 26 25 26 29 6 8 7 15 32 9 27 11 34 31 35 6 25 4 35 40 12 2 39 34 21 8 48 8 49 1 39 32 30 46 10 1 45 29 2 17 31 22 30 16 59 10 63 15 71 53 28 50 46 29 59 53 5 3 5 83 48 50 39 18 24 76 6 65 28 72 81 38 54 8 35 88 89 89 18 99 9 99 76...

output:

150134230018

result:

ok 1 number(s): "150134230018"

Test #4:

score: 0
Accepted
time: 3ms
memory: 7892kb

input:

1000
1 1 2 2 4 2 7 3 8 1 9 4 4 4 4 15 3 12 12 6 21 10 20 19 14 23 3 24 26 26 25 31 2 25 28 27 22 38 29 37 16 26 40 5 7 4 25 38 18 41 47 45 14 53 45 18 18 5 10 26 24 59 31 27 58 59 20 47 58 38 29 34 67 68 42 51 44 4 79 7 45 8 73 82 36 51 38 44 77 80 70 21 15 76 40 82 60 61 17 94 46 1 46 25 83 56 57 1...

output:

291482220072

result:

ok 1 number(s): "291482220072"

Test #5:

score: 0
Accepted
time: 1ms
memory: 7948kb

input:

20
1 1 2 3 2 6 1 5 4 7 5 7 9 11 6 7 9 12 4
78702 90933 62714 66603 17557 48708 96257 69094 34701 81307 3224 81752 2616 58113 86806 5963 73405 5059 66996 97390

output:

34002240599

result:

ok 1 number(s): "34002240599"

Test #6:

score: 0
Accepted
time: 32ms
memory: 16080kb

input:

200000
1 2 2 3 1 5 5 8 3 3 1 1 5 13 3 10 15 18 13 5 3 12 18 15 8 8 21 13 4 5 15 8 27 24 20 17 8 26 4 21 36 32 36 42 25 41 25 8 22 37 51 13 26 6 41 26 28 41 13 51 37 35 1 35 28 25 66 14 49 40 24 46 38 20 8 6 15 35 40 2 26 57 65 53 51 17 23 41 14 17 80 54 74 7 32 43 13 49 29 16 17 13 45 51 51 18 20 75...

output:

215275813232282

result:

ok 1 number(s): "215275813232282"

Test #7:

score: 0
Accepted
time: 1ms
memory: 7992kb

input:

8
1 2 2 4 5 2 4
3 6 10 8 3 8 3 10

output:

172

result:

ok 1 number(s): "172"

Test #8:

score: 0
Accepted
time: 0ms
memory: 7760kb

input:

50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 27 28 15 6 7 26 12 3 6 1 24 30 29 16 16 18 18 2 8 9
8 17 17 18 25 2 10 45 29 38 6 33 35 44 18 50 12 4 16 20 42 3 19 47 33 31 24 28 42 14 3 28 9 8 21 18 25 37 19 49 2 16 41 9 43 31 6 16 2 11

output:

6044

result:

ok 1 number(s): "6044"

Test #9:

score: -100
Wrong Answer
time: 68ms
memory: 24180kb

input:

200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

7065581081920741

result:

wrong answer 1st numbers differ - expected: '7043264795053440', found: '7065581081920741'