QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#770507#7966. 采矿little_pinkpigWA 154ms81740kbC++144.8kb2024-11-21 22:08:022024-11-21 22:08:04

Judging History

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

  • [2024-11-21 22:08:04]
  • 评测
  • 测评结果:WA
  • 用时:154ms
  • 内存:81740kb
  • [2024-11-21 22:08:02]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define MAXN (305)
#define MAXQ (605)
using namespace std;
const ll inf=1e16;
template<typename type>
void read(type &x)
{
    bool f=0;char ch=0;x=0;
    while(ch<'0'||ch>'9'){f|=!(ch^'-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    x=f?-x:x;
}
template<typename type,typename... Args>
void read(type &x,Args &... args)
{
    read(x);
    read(args...);
}
int n,q,s,tot,pcnt;
int fa[MAXN],r[MAXN],p[MAXN],siz[MAXN],ind[MAXN],dfn[MAXN];
ll ans=-inf;
ll f[MAXN][MAXN][MAXN],g[MAXN][MAXN][MAXN],h[MAXN][MAXN];
vector<int> G[MAXN];
vector<ll> vec[2][MAXN];
inline bool chk(int u,int v){return dfn[v]>=dfn[u]&&dfn[v]<=dfn[u]+siz[u]-1;}
void dfs(int u)
{
    siz[ind[dfn[u]=++tot]=u]=1;
    for(int v:G[u]) if(v) dfs(v),siz[u]+=siz[v];
}
inline void mset()
{
    for(int i=1;i<=n;i++) for(int j=0;j<=siz[G[i][0]];j++) for(int k=0;k<=siz[G[i][1]];k++) f[i][j][k]=-inf;
    for(int i=1;i<=n;i++) for(int j=0;j<=n;j++) h[i][j]=-inf;
}
inline void cset(){for(int i=1;i<=n;i++) for(int j=0;j<=siz[G[i][0]];j++) for(int k=0;k<=siz[G[i][1]];k++) g[i][j][k]=f[i][j][k];}
inline ll calc(int u,int o,int v){if(!u) return 0;return vec[o][u][v];}
void work(int o)
{
    if(o==1)
    {
        for(int i=2;i<=n;i++)
            for(int j=0;j<=siz[G[i][0]];j++)
                for(int k=0;k<=siz[G[i][1]];k++)
                    if(pcnt-j-k<n-siz[i])
                        h[i][j+k]=max(h[i][j+k],g[i][j][k]);

        for(int x=n,i;x;x--)
        {
            i=ind[x];
            for(int j=0;j<=siz[G[i][0]];j++)
            {
                for(int k=0;k<=siz[G[i][1]];k++)
                {
                    if(j+k<=pcnt&&pcnt-j-k<=n-siz[i])
                    {
                        if(G[i][0]) f[i][j][k]=max(f[i][j][k],h[G[i][0]][j]);
                        if(G[i][1]) f[i][j][k]=max(f[i][j][k],h[G[i][1]][k]);
                        if(pcnt-j-k<n-siz[i]) h[i][j+k]=max(h[i][j+k],f[i][j][k]);
                    }
                }
            }
        }
    }
    if(o==2)
    {
        for(int i=1;i<=n;++i)
        {
            for(int j=0;j<=siz[G[i][0]];j++)
            {
                for(int k=0;k<=siz[G[i][1]];k++)
                {
                    if(G[i][0]&&j<siz[G[i][0]]) h[G[i][0]][j]=max(h[G[i][0]][j],g[i][j][k]);
                    if(G[i][1]&&k<siz[G[i][1]]) h[G[i][1]][k]=max(h[G[i][1]][k],g[i][j][k]);
                }
            }
        }
        for(int x=n,i;x;x--)
        {
            i=ind[x];
            for(int j=0;j<=siz[G[i][0]];j++)
            {
                for(int k=0;k<=siz[G[i][1]];k++)
                {
                    f[i][j][k]=max(f[i][j][k],h[i][j+k]);
                    if(G[i][0]&&j<siz[G[i][0]]) h[G[i][0]][j]=max(h[G[i][0]][j],f[i][j][k]);
                    if(G[i][1]&&k<siz[G[i][1]]) h[G[i][1]][k]=max(h[G[i][1]][k],f[i][j][k]);
                }
            }
        }
    }
    if(o==3)
    {
        for(int i=1;i<=n;i++)
            for(int j=0;j<=siz[G[i][0]];j++)
                for(int k=0;k<=siz[G[i][1]];k++)
                    if(pcnt-j-k<n-siz[i])
                        f[i][j][k]=g[i][j][k];
        ++pcnt;
    }
    if(o==4)
    {
        for(int i=1;i<=n;i++)
            for(int j=0;j<=siz[G[i][0]];j++)
                for(int k=0;k<=siz[G[i][1]];k++)
                    if(pcnt-j-k>0)
                        f[i][j][k]=g[i][j][k];
        --pcnt;
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<=siz[G[i][0]];j++)
            for(int k=0;k<=siz[G[i][1]];k++)
                if(f[i][j][k]>=0)
                    f[i][j][k]+=calc(G[i][0],0,j)+calc(G[i][1],0,k)+calc(i,1,pcnt-j-k)+r[i];
    return;
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    read(n,q,s);
    for(int i=2;i<=n;i++) read(fa[i]),G[fa[i]].push_back(i);
    for(int i=2;i<=n;i++) read(r[i]);
    for(int i=2;i<=n;i++) read(p[i]);
    for(int i=1;i<=n;i++) while(G[i].size()<2) G[i].push_back(0);
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(chk(i,j)) vec[0][i].push_back(p[j]);
            else vec[1][i].push_back(p[j]);
        }
        for(int o=0;o<2;o++)
        {
            sort(vec[o][i].begin(),vec[o][i].end(),greater<int>());
            vec[o][i].insert(vec[o][i].begin(),0);
            for(int j=1;j<(int)vec[o][i].size();j++) vec[o][i][j]+=vec[o][i][j-1];
        }
    }
    mset();
    f[s][0][0]=0;
    for(int i=1,o;i<=q;++i)
    {
        read(o);
        cset(),mset(),work(o);
    }
    for(int i=1;i<=n;i++) for(int j=0;j<=siz[G[i][0]];j++) for(int k=0;k<=siz[G[i][1]];k++) ans=max(ans,f[i][j][k]);
    if(ans<0) printf("No solution.");
    else printf("%lld",ans);
}

详细

Test #1:

score: 0
Wrong Answer
time: 154ms
memory: 81740kb

input:

300 600 175
1 2 1 4 4 2 7 8 9 8 3 5 12 10 6 6 13 15 9 11 11 13 15 22 14 26 27 12 5 16 10 24 23 16 33 34 21 22 37 39 17 39 40 20 36 28 40 33 48 29 26 46 46 18 37 32 20 38 54 45 19 30 52 27 18 60 41 57 30 50 48 47 65 17 35 14 55 24 78 80 71 81 28 3 21 19 63 35 75 75 73 92 89 36 81 50 34 93 85 43 42 78...

output:

No solution.

result:

wrong answer 1st lines differ - expected: '4588927051034', found: 'No solution.'