QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #541664 | #8938. Crawling on a Tree | ucup-team3510# | WA | 2ms | 12120kb | C++20 | 1.4kb | 2024-08-31 20:26:08 | 2024-08-31 20:26:09 |
Judging History
answer
#include <bits/stdc++.h>
#define N 10011
#define ll long long
#define sht short
using namespace std;
sht f[N][N];ll g[N][N];
int n,M,c[N];
struct edge{int v,w,k;};
vector<edge> G[N];
sht nf[N],tf[N];ll ng[N],tg[N];
void dfs(int u,int F)
{
for(auto [v,w,k]:G[u])if(v^F)dfs(v,u);
f[u][0]=g[u][0]=0;
for(auto [v,w,k]:G[u])if(v^F)
{
for(int i=0;i<=M;++i)
{
for(int j=0;i+j<=M;++j)if(j+2*f[v][j]<=k)
{
nf[i+j]=min((int)nf[i+j],f[u][i]+f[v][j]);
ng[i+j]=min(ng[i+j],g[u][i]+g[v][j]+1ll*(j+2*f[v][j])*w);
}
}
for(int i=0;i<=M;++i)f[u][i]=nf[i],g[u][i]=ng[i],nf[i]=M+1,ng[i]=1e18;
}
for(int i=1;i<=M;++i)f[u][i]=min(f[u][i],f[u][i-1]);
for(int i=1;i<=M;++i)g[u][i]=min(g[u][i],g[u][i-1]);
for(int i=0;i<=M;++i)f[u][i]=max((int)f[u][i],c[u]-i);
// printf("f[%d]:",u);for(int i=0;i<=M;++i)printf("%d ",(int)f[u][i]);putchar(10);
// printf("g[%d]:",u);for(int i=0;i<=M;++i)printf("%lld ",g[u][i]);putchar(10);
}
int main()
{
scanf("%d%d",&n,&M);
for(int i=1;i<n;++i)
{
int u,v,w,k;scanf("%d%d%d%d",&u,&v,&w,&k);G[u].push_back({v,w,k});G[v].push_back({u,w,k});
}
c[1]=0;for(int i=2;i<=n;++i)scanf("%d",c+i);
for(int i=1;i<=n;++i)for(int j=0;j<=M;++j)f[i][j]=M+1,g[i][j]=1e18;
for(int i=0;i<=M;++i)nf[i]=M+1,ng[i]=1e18;
dfs(1,0);
for(int i=1;i<=M;++i)
{
ll ans=1e18;
for(int j=0;j<=M;++j)if(j+f[1][j]<=i)ans=min(ans,g[1][j]);
if(ans<1e18)printf("%lld\n",ans);
else printf("-1\n");
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7972kb
input:
4 2 1 2 3 2 2 3 2 1 2 4 5 1 1 1 1
output:
-1 13
result:
ok 2 number(s): "-1 13"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5892kb
input:
4 2 1 2 3 2 2 3 2 1 2 4 5 1 2 2 2
output:
-1 -1
result:
ok 2 number(s): "-1 -1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7900kb
input:
2 1 2 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5960kb
input:
2 50 2 1 1 1 50
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
ok 50 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 5964kb
input:
2 50 2 1 1 50 50
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 50
result:
ok 50 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 5964kb
input:
2 50 1 2 1 100000 50
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 50
result:
ok 50 numbers
Test #7:
score: -100
Wrong Answer
time: 2ms
memory: 12120kb
input:
50 1 1 2 85524 58896 2 3 9137 9819 3 4 3036 88987 4 5 78909 15766 5 6 76067 34996 6 7 64247 63701 7 8 14 9384 8 9 37698 35418 9 10 51427 91691 10 11 39818 89351 11 12 47887 64083 12 13 43836 44135 13 14 22561 83803 14 15 52617 97413 15 16 41869 83810 16 17 35783 18642 17 18 5514 34601 18 19 50448 49...
output:
-1
result:
wrong answer 1st numbers differ - expected: '3202064', found: '-1'