QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#765142#5139. DFS Order 2frankly6WA 1ms5736kbC++172.7kb2024-11-20 12:31:362024-11-20 12:31:37

Judging History

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

  • [2024-11-20 12:31:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5736kb
  • [2024-11-20 12:31:36]
  • 提交

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);
}

详细

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'