QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#765142 | #5139. DFS Order 2 | frankly6 | WA | 1ms | 5736kb | C++17 | 2.7kb | 2024-11-20 12:31:36 | 2024-11-20 12:31:37 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int p=998244353;
const int MX=505;
const int inf=0x3fffffff;
int N;
int head[MX], cnt=0;
int fac[MX];
int dep[MX], siz[MX], son[MX], num[MX];
PII stac[MX]; int top=0;
int dp[MX][MX], ans[MX][MX];
int read()
{
int r=0, f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
return r*f;
}
struct edge{int nxt, to;}e[2*MX];
inline void ae(int u, int v){e[++cnt].to=v; e[cnt].nxt=head[u]; head[u]=cnt;}
void dfs(int x, int f)
{
dep[x]=dep[f]+1; siz[x]=1; num[x]=1;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==f) continue;
dfs(y,x);
siz[x]+=siz[y];
son[x]++;
num[x]=num[x]*num[y]%p;
}
if(son[x]) num[x]=num[x]*fac[son[x]]%p;
// cout << "x=" << x << ", siz=" << siz[x] << ", son=" << son[x] << ", num=" << num[x] << '\n';
}
void dfs2(int x, int f)
{
int sum=1;
for(int i=1;i<=top;i++)
if(stac[i].first!=inf) sum=sum*stac[i].second%p;
sum=sum*num[x]%p;
for(int i=0;i<=500;i++) dp[0][i]=0;
dp[0][0]=1;
// cout << "x=" << x << ", f=" << f << ", num=" << num[x] << '\n';
// for(int i=1;i<=top;i++) { auto u=stac[i]; cout << u.first << "&" << u.second << " "; } cout << '\n';
for(int i=1;i<=top;i++)
{
int v=stac[i].first, c=stac[i].second;
for(int j=0;j<=N;j++)
{
if(j>=v) dp[i][j]=dp[i-1][j]+dp[i-1][j-v];
else dp[i][j]=dp[i-1][j];
// cout << "dp[" << i << "][" << j << "]=" << dp[i][j] << '\n';
}
}
// for(int i=0;i+dep[x]<=N;i++) cout << dp[top][i] << " "; cout << '\n';
for(int i=0;i+dep[x]<=N;i++)
ans[x][i+dep[x]]=dp[top][i]*sum%p;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==f) continue;
stac[++top]={siz[y],num[y]};
}
PII tmp={inf,0};
for(int i=head[x],now=son[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==f) continue;
now--;
swap(stac[top-now],tmp);
dfs2(y,x);
swap(stac[top-now],tmp);
}
top-=son[x];
}
signed main()
{
// freopen("testdata.in","r",stdin);
fac[0]=1;
for(int i=1;i<=500;i++) fac[i]=fac[i-1]*i%p;
N=read();
for(int i=1;i<N;i++)
{
int u=read(), v=read();
ae(u,v); ae(v,u);
}
dfs(1,0);
dfs2(1,0);
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
cout << ans[i][j] << " ";
cout << '\n';
}
return (0-0);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5668kb
input:
5 1 2 1 3 3 4 3 5
output:
4 0 0 0 0 0 2 0 0 2 0 2 2 0 0 0 0 1 2 1 0 0 1 2 1
result:
ok 25 numbers
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5736kb
input:
10 9 2 9 6 10 5 1 5 1 6 9 3 5 8 4 3 7 9
output:
24 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 4 2 2 2 0 0 0 2 4 2 2 4 2 0 0 0 0 0 2 4 2 2 4 2 0 12 0 0 0 0 0 12 0 0 0 12 0 0 12 0 0 0 0 0 0 0 0 2 2 2 4 2 2 2 0 0 6 6 0 0 0 0 6 6 0 0 12 0 0 12 0 0 0 0 0 0 6 6 0 0 0 0 6 6
result:
wrong answer 14th numbers differ - expected: '4', found: '2'