QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #770550 | #7966. 采矿 | little_pinkpig | AC ✓ | 461ms | 444572kb | C++14 | 4.8kb | 2024-11-21 22:19:17 | 2024-11-21 22:19:18 |
Judging History
answer
#include<bits/stdc++.h>
#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=1,i;x<=n;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;
}
int 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: 100
Accepted
time: 218ms
memory: 442528kb
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:
4588927051034
result:
ok single line: '4588927051034'
Test #2:
score: 0
Accepted
time: 278ms
memory: 443916kb
input:
300 600 286 1 1 3 3 5 6 6 7 7 9 2 2 9 10 5 13 11 12 8 15 20 22 11 15 21 16 4 26 19 20 25 27 10 23 13 12 32 32 8 26 18 19 28 42 4 46 41 37 23 43 30 25 34 47 49 22 40 48 28 45 16 35 35 63 55 33 44 61 21 56 61 59 63 65 73 47 42 51 62 76 48 59 39 66 58 77 57 73 68 27 29 53 85 83 56 41 60 69 74 58 100 10...
output:
40349159313289
result:
ok single line: '40349159313289'
Test #3:
score: 0
Accepted
time: 461ms
memory: 444308kb
input:
301 600 153 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 ...
output:
44810792039851
result:
ok single line: '44810792039851'
Test #4:
score: 0
Accepted
time: 193ms
memory: 443456kb
input:
300 600 264 1 1 2 2 3 6 6 7 9 10 10 12 5 11 15 12 11 14 16 14 17 17 16 21 25 19 27 28 26 28 24 29 33 31 35 34 31 30 32 39 33 39 37 43 44 46 42 46 43 49 45 45 47 48 51 47 56 57 54 57 59 53 58 56 58 59 61 60 68 65 67 68 70 69 67 69 70 73 72 80 76 76 82 78 77 77 87 87 82 90 85 85 91 86 95 93 96 96 91 9...
output:
52315813623226
result:
ok single line: '52315813623226'
Test #5:
score: 0
Accepted
time: 202ms
memory: 443468kb
input:
300 600 33 1 1 2 4 4 2 5 5 9 9 8 11 10 12 13 13 15 11 18 19 18 16 19 22 17 22 21 23 28 25 29 27 29 34 28 30 31 36 38 34 39 39 35 44 36 42 38 45 41 45 43 52 44 52 51 48 55 56 55 56 60 57 54 60 58 66 59 63 63 61 68 67 68 65 72 71 74 76 72 80 73 74 83 81 82 81 79 87 86 85 91 86 88 88 94 89 90 94 98 97 ...
output:
48722943497148
result:
ok single line: '48722943497148'
Test #6:
score: 0
Accepted
time: 176ms
memory: 444040kb
input:
300 600 42 1 1 3 4 2 2 5 8 8 9 6 9 11 13 11 12 15 12 10 19 15 19 21 18 16 25 18 21 28 28 23 29 27 34 26 27 31 33 30 32 37 34 39 43 42 45 39 40 40 45 51 50 50 51 52 52 54 58 55 57 59 60 54 62 65 66 66 67 60 63 62 63 73 73 68 76 76 71 71 77 81 78 82 79 84 79 84 83 87 87 85 91 92 89 94 93 90 95 99 95 9...
output:
55427849622319
result:
ok single line: '55427849622319'
Test #7:
score: 0
Accepted
time: 187ms
memory: 444572kb
input:
300 600 137 1 2 1 3 2 6 7 6 4 8 11 5 11 5 13 12 10 10 12 17 13 18 22 18 21 20 20 23 23 27 27 29 25 29 33 35 36 31 33 35 40 40 43 44 39 43 41 46 42 46 49 44 53 52 55 54 51 55 51 59 56 61 54 62 61 59 64 62 60 68 67 63 65 73 72 73 72 75 74 79 77 80 78 76 77 83 78 80 88 89 86 90 89 91 90 93 92 97 95 95 ...
output:
53287628221118
result:
ok single line: '53287628221118'
Test #8:
score: 0
Accepted
time: 205ms
memory: 443900kb
input:
300 600 70 1 1 2 2 3 3 5 6 9 8 9 10 13 8 6 12 16 12 17 16 20 20 21 23 23 21 22 27 22 28 25 31 25 33 34 33 37 38 34 35 35 38 36 43 39 39 45 40 41 42 43 44 52 54 47 50 57 53 51 56 56 53 60 63 61 65 58 66 61 68 62 65 69 73 72 68 72 78 76 79 74 76 82 81 84 77 84 88 85 85 82 91 86 92 89 92 91 95 98 99 96...
output:
52245066034805
result:
ok single line: '52245066034805'
Test #9:
score: 0
Accepted
time: 170ms
memory: 444568kb
input:
300 600 56 1 2 2 4 3 6 1 7 7 6 5 11 8 12 12 10 9 14 13 11 14 13 18 21 20 25 18 21 20 27 24 32 32 33 29 30 28 30 37 40 33 36 34 38 41 38 47 48 44 43 48 51 53 50 49 56 52 56 55 52 57 54 60 63 61 60 61 68 65 70 63 66 70 69 67 72 77 77 72 73 80 78 81 81 80 78 82 88 88 89 90 89 90 91 86 87 97 91 93 97 94...
output:
54169471106772
result:
ok single line: '54169471106772'
Test #10:
score: 0
Accepted
time: 175ms
memory: 443964kb
input:
300 600 105 1 1 3 3 2 6 4 2 8 5 9 6 10 14 7 12 13 9 17 14 12 20 21 19 22 22 24 27 23 30 28 29 32 34 32 33 30 33 35 31 38 38 35 43 36 39 44 44 43 46 50 50 45 53 48 52 56 57 52 54 53 59 55 59 64 62 66 60 60 66 70 63 70 71 72 74 77 78 72 76 75 81 80 82 80 85 79 79 89 89 83 90 91 94 86 88 97 95 95 94 10...
output:
50990422314888
result:
ok single line: '50990422314888'
Test #11:
score: 0
Accepted
time: 192ms
memory: 443996kb
input:
300 600 99 1 2 3 1 3 5 6 6 2 8 11 10 9 13 10 14 13 16 17 17 19 19 20 15 21 18 18 27 29 28 23 29 30 34 31 35 32 31 37 40 34 40 42 42 39 38 47 48 43 47 51 46 49 50 51 48 49 58 50 54 52 62 60 57 63 63 64 68 62 66 70 67 69 71 66 74 71 76 76 77 81 75 81 77 85 84 82 85 89 86 82 87 92 94 86 96 90 97 90 96 ...
output:
50233132966129
result:
ok single line: '50233132966129'
Test #12:
score: 0
Accepted
time: 148ms
memory: 444092kb
input:
300 600 57 1 1 3 4 4 5 7 8 6 8 9 10 3 5 12 11 13 16 12 15 19 11 17 17 19 25 14 2 29 10 9 32 28 29 32 33 34 7 16 36 25 27 38 38 6 26 18 42 27 49 36 20 28 43 20 14 37 18 34 24 53 2 31 53 31 33 54 40 30 41 57 44 64 46 42 71 60 51 59 45 49 21 54 47 47 75 69 45 24 23 80 87 86 75 95 92 70 48 55 95 56 90 6...
output:
4351680767374
result:
ok single line: '4351680767374'
Test #13:
score: 0
Accepted
time: 172ms
memory: 443732kb
input:
300 600 111 1 2 1 4 3 6 5 8 7 5 10 12 7 11 6 14 17 12 13 13 20 14 21 23 17 18 23 20 29 28 22 30 28 34 34 31 35 29 31 32 36 37 40 37 39 43 43 41 40 49 44 46 44 48 49 48 53 55 53 51 52 62 59 55 63 66 60 65 65 70 67 69 66 71 73 67 73 77 76 72 72 80 77 83 82 84 84 82 88 90 83 87 88 87 93 96 92 93 98 98 ...
output:
50231080085638
result:
ok single line: '50231080085638'
Test #14:
score: 0
Accepted
time: 171ms
memory: 444228kb
input:
300 600 202 1 1 3 4 3 2 7 6 2 10 10 11 5 8 7 12 8 11 18 17 18 17 20 22 20 21 24 26 27 23 28 31 28 30 26 30 29 32 38 36 35 38 40 36 40 46 43 45 45 46 47 49 48 50 52 51 56 53 50 56 60 57 58 64 65 64 59 60 68 63 70 63 73 73 75 76 71 75 78 77 81 76 83 84 78 85 81 86 82 82 83 92 90 94 90 96 91 93 94 91 9...
output:
47868585292289
result:
ok single line: '47868585292289'
Test #15:
score: 0
Accepted
time: 115ms
memory: 444020kb
input:
301 600 150 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 9...
output:
1557184330900
result:
ok single line: '1557184330900'
Test #16:
score: 0
Accepted
time: 128ms
memory: 444280kb
input:
300 600 191 1 2 3 2 4 4 6 6 8 9 3 7 13 7 13 11 14 12 15 15 21 16 14 22 25 22 24 23 21 26 28 27 28 33 30 33 32 36 30 31 32 35 37 43 40 45 39 40 41 41 48 46 46 54 53 55 57 49 50 59 60 59 61 57 61 65 66 64 63 63 64 66 71 73 74 69 71 74 76 79 76 79 81 78 85 86 83 87 83 87 86 84 90 92 91 96 90 93 92 91 9...
output:
No solution.
result:
ok single line: 'No solution.'
Test #17:
score: 0
Accepted
time: 173ms
memory: 444144kb
input:
300 600 189 1 2 2 4 4 1 5 5 8 7 11 12 12 7 15 15 8 18 10 13 21 20 22 16 21 22 20 19 24 23 30 28 29 34 29 30 37 38 38 36 32 42 34 35 41 40 39 40 47 48 45 49 48 53 49 47 55 57 53 51 56 54 59 64 56 59 64 65 62 62 66 71 70 66 70 67 69 73 77 77 76 73 80 84 81 79 87 79 83 84 85 83 87 94 94 93 88 97 90 92 ...
output:
No solution.
result:
ok single line: 'No solution.'
Test #18:
score: 0
Accepted
time: 118ms
memory: 443964kb
input:
300 600 271 1 2 2 4 4 5 1 8 9 5 11 3 12 7 11 7 16 9 19 19 16 8 3 24 25 25 27 14 10 15 17 15 32 20 29 26 26 28 23 33 23 28 41 35 27 44 32 47 17 44 6 50 52 35 54 10 45 55 43 52 13 21 46 42 20 42 47 60 64 67 39 21 57 56 63 55 71 18 22 54 43 57 34 56 36 51 59 68 53 59 74 34 76 69 94 48 13 41 53 64 12 18...
output:
No solution.
result:
ok single line: 'No solution.'
Test #19:
score: 0
Accepted
time: 185ms
memory: 443884kb
input:
300 600 64 1 1 3 3 2 5 5 8 8 9 6 12 4 12 15 14 16 16 14 2 13 18 6 15 7 13 18 22 20 10 24 31 20 26 26 31 32 33 37 24 36 37 10 27 33 7 42 44 22 38 38 9 49 32 55 53 21 19 57 35 43 55 51 21 34 62 17 43 48 68 53 47 65 69 50 72 70 47 25 40 67 50 39 77 45 60 36 81 29 65 58 41 41 63 72 60 83 56 97 19 68 90 ...
output:
No solution.
result:
ok single line: 'No solution.'
Test #20:
score: 0
Accepted
time: 97ms
memory: 444212kb
input:
300 600 170 1 2 3 2 1 6 7 4 7 4 10 9 5 10 11 9 5 17 17 16 3 19 20 8 13 8 20 12 19 22 28 28 29 14 22 11 29 25 14 6 13 40 36 35 45 18 37 12 47 31 15 26 25 41 49 26 31 53 53 34 21 45 23 42 58 47 61 66 59 39 61 66 44 21 48 75 50 27 77 48 77 56 60 75 63 62 86 84 67 71 38 51 81 30 37 85 89 80 87 36 78 52 ...
output:
No solution.
result:
ok single line: 'No solution.'
Test #21:
score: 0
Accepted
time: 140ms
memory: 444128kb
input:
300 600 214 1 1 3 3 5 5 4 4 9 10 7 9 13 11 7 8 15 10 16 11 18 17 22 23 12 18 16 25 23 24 12 15 24 14 21 31 36 21 17 39 39 36 30 20 32 26 45 38 46 8 49 22 30 28 33 49 50 58 27 44 32 46 58 44 37 48 38 28 43 13 62 66 31 14 35 63 74 34 68 25 42 26 76 76 19 41 85 56 29 78 63 61 82 59 64 6 62 65 97 43 51 ...
output:
4485712836520
result:
ok single line: '4485712836520'
Test #22:
score: 0
Accepted
time: 0ms
memory: 16196kb
input:
6 3 2 1 2 3 3 2 45 38 27 44 79 5 3 5 5 9 1 2 3
output:
163
result:
ok single line: '163'
Test #23:
score: 0
Accepted
time: 139ms
memory: 444084kb
input:
300 600 296 1 1 3 4 4 5 7 7 6 3 5 12 12 13 2 10 13 2 8 20 15 21 16 16 24 24 8 26 18 22 18 27 21 34 10 34 20 38 25 38 28 36 28 22 6 40 40 42 15 44 44 29 29 9 41 50 57 43 50 57 42 32 62 46 14 60 56 9 41 30 71 60 63 54 48 65 73 74 14 27 63 72 25 66 56 71 43 23 32 70 83 48 88 49 26 47 85 53 39 23 45 98 ...
output:
4411111707253
result:
ok single line: '4411111707253'
Test #24:
score: 0
Accepted
time: 136ms
memory: 444240kb
input:
300 600 110 1 1 2 3 2 4 6 3 6 10 7 7 13 4 8 9 11 14 15 9 15 19 13 5 21 5 8 11 23 18 10 26 22 23 16 30 34 20 20 22 34 36 33 31 16 21 40 19 17 43 31 35 14 35 12 12 30 26 50 51 59 59 56 43 44 55 18 48 46 29 62 28 28 44 50 25 65 71 74 77 61 55 25 39 80 84 71 74 62 80 63 48 67 17 69 76 87 38 82 83 27 51 ...
output:
4479248027267
result:
ok single line: '4479248027267'
Test #25:
score: 0
Accepted
time: 142ms
memory: 443792kb
input:
300 600 254 1 2 1 3 2 6 3 7 8 10 9 5 4 12 5 16 6 13 13 4 18 10 11 14 8 23 7 16 22 18 15 26 25 31 19 11 29 29 35 20 41 42 14 25 23 35 33 24 36 33 27 15 40 48 41 39 39 46 19 12 36 51 34 37 61 58 22 58 42 64 32 20 28 9 72 60 76 49 46 70 47 61 69 80 45 69 76 79 44 90 86 34 77 60 71 48 64 66 43 86 92 53 ...
output:
4532069466798
result:
ok single line: '4532069466798'
Test #26:
score: 0
Accepted
time: 149ms
memory: 444144kb
input:
300 600 274 1 1 2 4 3 4 2 7 9 7 11 9 10 3 8 16 5 17 16 10 5 14 23 22 24 25 24 27 28 11 8 22 27 6 12 18 20 12 6 23 15 41 26 34 29 20 37 14 18 41 35 37 31 43 29 32 15 26 47 42 19 32 17 35 21 30 65 68 36 28 49 13 70 58 49 65 75 55 61 47 54 55 82 46 58 60 68 73 39 64 25 75 50 31 45 50 66 97 73 53 82 94 ...
output:
37149511717824
result:
ok single line: '37149511717824'
Test #27:
score: 0
Accepted
time: 141ms
memory: 444148kb
input:
300 600 262 1 2 1 4 5 5 3 7 7 6 11 8 3 11 2 16 9 17 8 19 12 13 20 14 9 6 4 16 17 24 29 30 32 15 23 18 23 19 33 21 31 12 36 29 44 36 41 45 31 18 33 25 35 39 46 50 46 52 35 38 52 61 32 39 59 27 30 57 63 43 56 28 45 50 63 74 64 61 71 79 56 60 69 27 13 20 87 28 76 10 82 75 15 21 24 70 43 94 58 75 69 55 ...
output:
38295501087283
result:
ok single line: '38295501087283'