QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#85076#5683. 大富翁Crysfly🌈AC ✓116ms31784kbC++203.1kb2023-03-06 22:24:442023-03-06 22:24:47

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 22:24:47]
  • Judged
  • Verdict: AC
  • Time: 116ms
  • Memory: 31784kb
  • [2023-03-06 22:24:44]
  • Submitted

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
#define ull unsigned long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define mod 998244353
struct modint{
    int x;
    modint(int o=0){x=o;}
    modint &operator = (int o){return x=o,*this;}
    modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
    modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
    modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
    modint &operator ^=(int b){
        modint a=*this,c=1;
        for(;b;b>>=1,a*=a)if(b&1)c*=a;
        return x=c.x,*this;
    }
    modint &operator /=(modint o){return *this *=o^=mod-2;}
    friend modint operator +(modint a,modint b){return a+=b;}
    friend modint operator -(modint a,modint b){return a-=b;}
    friend modint operator *(modint a,modint b){return a*=b;}
    friend modint operator /(modint a,modint b){return a/=b;}
    friend modint operator ^(modint a,int b){return a^=b;}
    friend bool operator ==(modint a,int b){return a.x==b;}
    friend bool operator !=(modint a,int b){return a.x!=b;}
    bool operator ! () {return !x;}
    modint operator - () {return x?mod-x:0;}
    bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
    if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
    int m=iv.size(); ++n;
    if(m>=n)return;
    iv.resize(n),fac.resize(n),ifac.resize(n);
    For(i,m,n-1){
        iv[i]=iv[mod%i]*(mod-mod/i);
        fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
    }
}
inline modint C(int n,int m){
    if(m<0||n<m)return 0;
    return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair 
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

int n,fa[maxn],dep[maxn],res,w[maxn],sz[maxn],p[maxn];
vi e[maxn];

void dfs(int u){
    sz[u]=1;
    for(int v:e[u]){
        dep[v]=dep[u]+1;
        dfs(v);
        sz[u]+=sz[v];
    }
}

int col[maxn];
int cnt[maxn];
void solve(int u){
    for(int v:e[u]){
        solve(v);
        cnt[u]+=cnt[v];
    }
    if(col[u]){
        res+=w[u];
        res+=cnt[u];
    }else{
        res-=(sz[u]-1);
        res+=cnt[u];
        cnt[u]++;
    }
}

signed main()
{
    n=read();
    For(i,1,n)w[i]=-read();
    For(i,2,n)fa[i]=read(),e[fa[i]].pb(i);
    dfs(1);
    For(i,1,n)p[i]=i;
    sort(p+1,p+n+1,[&](int x,int y){
        return w[x]+sz[x]-dep[x]>w[y]+sz[y]-dep[y];
    });
    
    For(i,1,n) col[p[i]]=i&1;
//	For(i,1,n) cout<<col[i]<<" ";puts("");
    solve(1);
    cout<<res;
    return 0;
}
/*
7
0 0 1 0 0 0 0
1 1 2 2 3 3
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 7928kb

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: 8072kb

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: 0ms
memory: 8128kb

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: 3ms
memory: 8020kb

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: 79ms
memory: 22716kb

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: 86ms
memory: 22712kb

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: 71ms
memory: 22628kb

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: 57ms
memory: 22792kb

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: 86ms
memory: 22732kb

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: 5ms
memory: 9160kb

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: 17ms
memory: 20744kb

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: 30ms
memory: 20616kb

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: 26ms
memory: 20428kb

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: 48ms
memory: 20732kb

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: 0ms
memory: 8344kb

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: 110ms
memory: 31600kb

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: 112ms
memory: 31784kb

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: 116ms
memory: 31604kb

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: 102ms
memory: 31620kb

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: 1ms
memory: 8944kb

input:

7
0 0 1 0 0 0 0
1 1 2 2 3 3

output:

2

result:

ok single line: '2'