QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85187 | #5683. 大富翁 | fengyuyue | AC ✓ | 57ms | 12072kb | C++14 | 3.5kb | 2023-03-07 08:44:49 | 2023-03-07 08:44:52 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define gc getchar
#define pc putchar
#define pii pair<int,int>
#define pil pair<int,long long>
#define pli pair<long long,int>
#define pll pair<long long,long long>
#define For(i,l,r) for(int i=(l);i<=(r);i++)
#define IFor(i,r,l) for(int i=(r);i>=(l);i--)
#define for_son(u) for(int e=head[u];e;e=nxt[e])
#define eps (1e-8)
#define INF 0x3f3f3f3f
using namespace std;
char aa;
namespace ljh
{
namespace IO
{
// const int SIZ=1<<20;
// char ibuf[SIZ],*p1,*p2,obuf[SIZ],*p3=obuf;
// #define gc() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,SIZ,stdin),p1==p2)?EOF:*p1++)
// void pc(const char &c)
// {
// if(p3-obuf==SIZ) fwrite(obuf,1,SIZ,stdout),p3=obuf;
// *p3++=c;
// }
int rd()
{
int x=0,f=1;
char ch=gc();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=gc();
}
while(isdigit(ch)){
x=x*10+ch-'0';
ch=gc();
}
return x*f;
}
void wr(int x,char ch)
{
if(x<0) x=-x,pc('-');
static char st[12];
int top=0;
do{
st[top++]=x%10+'0',x/=10;
}while(x);
while(top) pc(st[--top]);
pc(ch);
}
ll ll_rd()
{
ll x=0;
int f=1;
char ch=gc();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=gc();
}
while(isdigit(ch)){
x=x*10+ch-'0';
ch=gc();
}
return x*f;
}
void ll_wr(ll x,char ch)
{
if(x<0) x=-x,pc('-');
static char st[22];
int top=0;
do{
st[top++]=x%10+'0',x/=10;
}while(x);
while(top) pc(st[--top]);
pc(ch);
}
}
using namespace IO;
const int N=2e5+5,mod=0;
namespace tem
{
int qpow(int a,int b,int p)
{
a%=p;
int res=1;
while(b){
if(b&1) res=1ll*res*a%p;
a=1ll*a*a%p;
b>>=1;
}
return res;
}
int get_inv(int x){return qpow(x,mod-2,mod);}
int lowbit(int x){return x&(-x);}
void add(int &x,const int y){ x=(x+y>=mod?x+y-mod:x+y); }
// int get(int x) {return fa[x]==x?x:fa[x]=get(fa[x])};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
}
using namespace tem;
int n,w[N];
int cnt=1,head[N],nxt[N<<1],to[N<<1];
int siz[N],dep[N],p[N];
#define val(a) (siz[a]-dep[a]-w[a])
bool cmp(const int &a,const int &b)
{
return val(a)>val(b);
}
void add_edge(int u,int v){nxt[++cnt]=head[u],to[cnt]=v,head[u]=cnt;}
void dfs(int u)
{
siz[u]=1;
for_son(u){
int v=to[e];
dep[v]=dep[u]+1;
dfs(v);
siz[u]+=siz[v];
}
}
void main()
{
n=rd();
For(i,1,n) w[i]=rd();
For(i,2,n){
int fa=rd();
add_edge(fa,i);
}
dep[1]=1;
dfs(1);
For(i,1,n) p[i]=i;
sort(p+1,p+n+1,cmp);
ll ans=0;
for(int i=1;i<=n;i+=2) ans+=val(p[i]);
ll_wr(ans,'\n');
// fwrite(obuf,1,p3-obuf,stdout);
}
/*
*/
}
char bb;
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// int st=clock();
ljh::main();
// int ed=clock();
// cerr<<ed-st<<"ms"<<endl;
// cerr<<(&bb-&aa)/1024/1024<<"MB"<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3376kb
input:
8 0 1 1 0 0 0 0 0 3 1 8 4 1 3 1
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
10 1 0 0 0 0 0 0 0 0 1 8 1 9 10 9 8 4 5 1
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3428kb
input:
8 1 0 1 0 0 1 0 0 1 6 2 1 2 1 5
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3304kb
input:
8 0 0 0 1 1 0 1 1 7 1 3 4 1 4 3
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
10 0 0 1 0 0 0 0 1 1 0 1 5 1 1 9 1 2 4 4
output:
3
result:
ok single line: '3'
Test #6:
score: 0
Accepted
time: 27ms
memory: 8868kb
input:
199998 2 2 3 2 1 3 0 2 0 3 2 0 2 2 1 1 3 3 3 3 2 0 1 2 0 3 1 1 0 0 3 3 3 3 0 3 2 2 1 1 2 2 0 3 3 3 1 2 0 2 2 1 2 0 3 2 0 0 0 3 2 3 0 1 1 2 0 2 2 0 3 1 1 2 3 1 0 3 0 2 1 0 3 3 1 1 2 3 1 0 3 0 1 2 3 1 3 3 0 3 1 2 1 1 3 2 1 3 3 3 1 1 2 3 2 0 2 3 2 2 1 1 2 1 2 0 1 0 1 3 3 2 3 2 0 3 2 2 2 0 3 2 1 2 3 1 2...
output:
-101057
result:
ok single line: '-101057'
Test #7:
score: 0
Accepted
time: 31ms
memory: 8872kb
input:
199992 2 2 0 0 2 0 1 2 1 2 2 1 1 2 1 1 3 0 0 3 1 0 2 0 0 1 0 3 2 0 2 3 2 3 2 0 3 2 2 2 3 2 1 3 1 1 2 3 1 2 0 0 2 2 0 3 1 1 0 1 1 1 0 2 3 0 3 0 3 1 3 2 3 1 0 3 2 2 3 1 3 0 2 2 0 3 2 2 1 1 0 1 2 0 1 3 1 2 1 1 3 3 1 2 1 3 0 1 1 1 2 1 2 0 2 0 0 0 2 0 0 3 1 3 0 1 1 0 3 1 1 2 3 1 1 0 2 0 3 2 1 2 0 2 1 0 0...
output:
-63508
result:
ok single line: '-63508'
Test #8:
score: 0
Accepted
time: 32ms
memory: 9048kb
input:
199993 2 3 0 1 3 3 2 1 0 2 2 0 3 1 2 2 1 2 2 3 0 1 0 0 2 1 1 3 2 1 0 2 1 2 2 3 3 3 1 2 2 2 1 3 2 2 0 2 3 3 2 1 3 0 1 3 3 2 1 1 3 0 2 2 0 3 1 3 2 0 1 1 3 0 0 2 3 2 1 0 1 1 3 0 1 0 2 3 2 1 0 3 2 2 3 1 3 2 2 0 1 2 2 0 2 1 2 0 1 1 1 2 2 3 2 1 2 2 0 0 2 3 3 1 1 0 3 2 2 3 1 3 2 1 3 0 2 3 0 3 0 3 3 2 1 2 2...
output:
-72819
result:
ok single line: '-72819'
Test #9:
score: 0
Accepted
time: 36ms
memory: 8896kb
input:
200000 0 2 2 2 2 3 2 1 2 3 3 1 2 1 0 1 2 1 2 3 1 2 2 3 3 3 2 2 0 3 3 0 0 1 3 3 0 1 0 1 0 0 2 0 1 3 1 0 1 2 1 1 1 2 1 3 3 3 2 2 1 2 0 2 1 0 3 2 1 0 0 3 1 3 1 0 2 0 1 3 2 1 3 3 2 3 3 1 3 2 2 0 0 1 2 0 3 3 1 0 3 2 1 3 1 3 0 0 2 3 1 2 3 0 0 0 2 3 1 0 1 1 3 2 2 6 3 2 2 0 2 1 0 2 3 0 0 0 1 2 3 1 1 1 2 2 3...
output:
-87803
result:
ok single line: '-87803'
Test #10:
score: 0
Accepted
time: 47ms
memory: 8920kb
input:
199994 69536 93956 146435 58370 55904 55731 40099 34869 22948 62455 25557 61814 118354 34694 37607 102825 86029 141405 6587 18273 174985 101354 139220 168750 14953 92256 162412 164115 172096 52676 126381 152299 140824 180431 131743 128463 115582 173595 160676 168294 26378 66194 115896 193154 79199 4...
output:
-10000211244
result:
ok single line: '-10000211244'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
31 0 2 0 1 0 1 2 2 0 1 2 0 2 2 1 2 1 0 0 0 2 1 2 0 1 0 0 2 0 1 0 15 2 13 15 8 30 15 25 25 2 13 1 13 1 30 1 2 30 11 2 13 13 11 13 1 15 12 16 15 15
output:
-6
result:
ok single line: '-6'
Test #12:
score: 0
Accepted
time: 19ms
memory: 8132kb
input:
199992 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
20452
result:
ok single line: '20452'
Test #13:
score: 0
Accepted
time: 10ms
memory: 8300kb
input:
199996 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 0...
output:
20009
result:
ok single line: '20009'
Test #14:
score: 0
Accepted
time: 22ms
memory: 8072kb
input:
199996 3 1 1 0 3 0 1 3 0 3 1 3 1 0 2 0 3 3 1 2 0 3 3 0 2 2 0 2 3 1 3 0 0 3 1 0 0 1 2 1 3 2 3 0 2 1 2 0 1 0 3 1 3 2 0 1 1 3 3 1 2 2 3 2 1 0 3 0 3 0 0 2 3 3 2 0 0 1 2 1 3 3 0 0 1 2 2 0 1 1 3 3 1 3 1 0 1 0 0 0 1 0 1 2 1 0 1 2 2 0 2 3 0 1 3 2 1 0 3 3 3 3 0 3 0 3 0 3 1 2 0 3 1 2 3 2 0 1 2 1 1 3 2 1 0 1 1...
output:
-100430
result:
ok single line: '-100430'
Test #15:
score: 0
Accepted
time: 45ms
memory: 8288kb
input:
199999 129505 14159 194788 69896 53179 103846 110185 158026 53493 4149 158821 181222 159742 175140 155608 37494 112878 78442 152990 5490 101005 39752 164304 162429 83386 88164 31144 84029 173037 92918 2500 103066 137572 20077 50183 115122 158847 51492 130020 193352 195330 30765 183180 118688 125622 ...
output:
-10014348789
result:
ok single line: '-10014348789'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3376kb
input:
21 0 0 0 2 1 1 0 2 2 2 2 0 0 1 2 2 1 0 0 2 1 17 9 3 4 1 11 15 19 4 8 10 11 7 6 6 14 2 2 12 20
output:
-12
result:
ok single line: '-12'
Test #17:
score: 0
Accepted
time: 57ms
memory: 11920kb
input:
199995 18 17 17 5 17 15 14 20 7 18 10 15 18 15 15 7 18 13 16 11 5 14 9 9 18 20 5 9 15 15 3 12 4 20 10 1 9 3 1 0 12 1 16 17 19 8 16 17 19 8 11 19 12 10 13 6 4 4 9 19 17 14 6 0 18 2 15 9 7 0 4 17 20 14 10 6 7 0 5 11 2 7 16 5 14 12 2 11 7 17 5 1 0 17 14 20 19 16 2 19 2 16 5 6 2 4 13 6 5 4 12 13 11 7 5 ...
output:
-3519230
result:
ok single line: '-3519230'
Test #18:
score: 0
Accepted
time: 42ms
memory: 11904kb
input:
199991 17 4 13 20 14 9 9 6 5 2 20 4 5 10 5 2 8 3 16 8 2 0 18 20 19 16 10 13 19 9 12 19 11 13 14 6 11 16 20 12 5 11 16 14 19 18 3 0 13 6 1 14 13 14 14 8 13 15 3 3 5 11 9 10 15 6 6 4 16 19 17 18 15 9 6 14 12 20 15 6 19 6 15 11 1 9 16 4 8 0 4 2 13 16 5 15 12 14 20 12 20 11 15 18 7 6 17 4 20 11 8 4 6 9 ...
output:
-3391196
result:
ok single line: '-3391196'
Test #19:
score: 0
Accepted
time: 47ms
memory: 12072kb
input:
199990 8 20 5 15 1 2 9 1 14 1 10 13 0 20 18 10 3 12 13 19 1 7 2 3 12 5 2 12 13 8 16 3 4 4 17 19 9 10 14 20 5 6 13 12 4 20 19 9 10 5 9 9 2 17 17 2 10 2 2 12 20 14 11 2 1 16 15 0 2 5 1 20 11 19 5 20 16 14 9 14 5 13 17 19 3 13 8 7 13 4 15 12 16 19 18 19 3 15 4 14 5 15 14 3 19 5 13 5 15 6 17 3 10 14 1 6...
output:
-3235337
result:
ok single line: '-3235337'
Test #20:
score: 0
Accepted
time: 42ms
memory: 12032kb
input:
199997 18 18 7 20 11 13 2 3 3 15 16 13 15 17 16 5 3 9 16 18 13 7 17 5 11 0 9 14 11 5 19 4 19 12 6 15 17 18 4 13 15 1 16 16 16 18 7 0 1 17 5 3 1 13 1 12 12 0 1 20 9 17 13 0 3 9 7 0 9 9 6 1 0 5 18 9 15 1 3 0 11 3 12 20 10 7 17 1 4 11 6 12 6 4 17 5 5 12 1 12 3 2 16 11 13 13 13 18 2 1 17 0 11 11 19 11 1...
output:
-3568351
result:
ok single line: '-3568351'
Test #21:
score: 0
Accepted
time: 2ms
memory: 3376kb
input:
7 0 0 1 0 0 0 0 1 1 2 2 3 3
output:
2
result:
ok single line: '2'