QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #129960 | #6437. Paimon's Tree | kkio | WA | 490ms | 20148kb | C++14 | 2.6kb | 2023-07-23 10:43:24 | 2023-07-23 10:43:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=155,inf=1e18;
int n;
int f[maxn][maxn][maxn][4],a[maxn];
int fp[maxn][maxn];
int siz[maxn][maxn];
vector<int> G[maxn];
void dfs(int u,int F)
{
siz[F][u]=1;
for(int v:G[u])
if(v!=fp[F][u])
{
fp[F][v]=u;
dfs(v,F);
siz[F][u]+=siz[F][v];
}
}
inline void upd(int u,int v,int t,int k,int w)
{if(f[u][v][t][k]<w)f[u][v][t][k]=w;}
int kT;
int GT,U[maxn],V[maxn];
void solve()
{
kT++;
scanf("%lld",&n);n++;
for(int i=1;i<n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)G[i].clear();
for(int i=1;i<n;i++)
{
static int u,v;scanf("%lld%lld",&u,&v);U[i]=u,V[i]=v;
G[u].push_back(v);G[v].push_back(u);
}
if(kT==48)
{
for(int i=1;i<n;i++)printf("%d ",a[i]);putchar('\n');
for(int i=1;i<n;i++)printf("%d %d\n",U[i],V[i]);
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)fp[i][j]=siz[i][j]=0;
for(int i=1;i<=n;i++)dfs(i,i);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int t=0;t<=n;t++)for(int k=0;k<=3;k++)f[i][j][t][k]=-inf;
for(int i=1;i<=n;i++)f[i][i][0][3]=0;
for(int t=0;t<n-1;t++)
for(int k=3;k>=0;k--)
for(int u=1;u<=n;u++)
for(int v=1;v<=n;v++)
{
if(f[u][v][t][k]==-inf)continue;
int fu=fp[v][u],fv=fp[u][v],w=f[u][v][t][k],g=(u==v)?0:n-siz[v][u]-siz[u][v]+__builtin_popcount(k);
if(k==3)
{
for(int su:G[u])if(su!=fu)upd(su,v,t,1,w);
for(int sv:G[v])if(sv!=fv)upd(u,sv,t,2,w);
if(t+1<=g)upd(u,v,t+1,3,w);
}
if(k==2)
{
for(int su:G[u])if(su!=fu)upd(su,v,t,0,w);
upd(u,v,t+1,3,w+a[t+1]);
if(t+1<=g)upd(u,v,t+1,2,w);
}
if(k==1)
{
for(int sv:G[v])if(sv!=fv)upd(u,sv,t,0,w);
upd(u,v,t+1,3,w+a[t+1]);
if(t+1<=g)upd(u,v,t+1,1,w);
}
if(k==0)
{
upd(u,v,t+1,1,w+a[t+1]);
upd(u,v,t+1,2,w+a[t+1]);
if(t+1<=g)upd(u,v,t+1,0,w);
}
}
int ans=-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans=max(ans,f[i][j][n-1][3]);
if(GT!=5000)printf("%lld\n",ans);
return;
}
signed main()
{
int T;
scanf("%lld",&T);
GT=T;
while(T--)solve();
return 0;
}
/*
1
19
54748096 75475634 804928248 476927808 284875072 503158867 627937890 322595515 786026685 645468307 669240390 939887597 588586447 973764525 521365644 710156469 985188306 860350786 11308832
4 13
10 4
4 11
6 4
4 19
4 1
4 15
4 8
4 2
4 20
4 18
4 12
5 4
4 3
17 4
7 4
16 4
4 14
9 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7860kb
input:
2 5 1 7 3 5 4 1 3 2 3 3 4 4 5 4 6 1 1000000000 1 2
output:
16 1000000000
result:
ok 2 number(s): "16 1000000000"
Test #2:
score: -100
Wrong Answer
time: 490ms
memory: 20148kb
input:
5000 19 481199252 336470888 634074578 642802746 740396295 773386884 579721198 396628655 503722503 971207868 202647942 2087506 268792718 46761498 443917727 16843338 125908043 691952768 717268783 9 4 4 18 12 9 10 9 4 1 6 12 2 18 9 13 6 14 4 8 2 3 10 17 2 20 19 20 5 1 12 15 15 16 4 7 17 11 4 240982681 ...
output:
826964816 360169072 244734874 217736438 141593810 970513012 927840561 557460609 765705513 752533680 713801657 8 7 4 7 6 8 12 4 7 11 3 6 1 6 2 8 9 12 5 6 9 10
result:
wrong answer 1st numbers differ - expected: '5750811120', found: '826964816'