QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#282720#7610. Bus Lineslight_ink_dotsWA 4ms10516kbC++143.0kb2023-12-12 20:57:592023-12-12 20:58:00

Judging History

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

  • [2023-12-12 20:58:00]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:10516kb
  • [2023-12-12 20:57:59]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=3e5+100;
const int mod=1e9+7;
#define int long long
int n;
vector<int>v[N];
int dp[N][20],g[N][20],h[N];
int f[N];
int mex(const vector<int>&a){
    static int vis[30];
    memset(vis,0,sizeof(vis));
    for(int x:a)
        for(int i=0;i<=x;i++) vis[i]++;
    for(int k=0;k<=20;k++){
        for(int j=0;j<=k;j++){
            if(vis[j]-(k+1)+j<0)return k;
        }
    }
}
void pfs(int x,int fa){
    vector<int>s;
    for(auto y:v[x]){
        if(y==fa) continue;
        pfs(y,x);
        s.push_back(f[y]);
    }
    f[x]=mex(s);
    // cerr<<"? "<<x<<" "<<f[x]<<endl;
}
int d[N][20],tg[N][20];
void dfs(int x,int fa){
    vector<int>out;
    for(int y:v[x]) if(y!=fa) out.push_back(y);
    sort(out.begin(),out.end(),[&](int u,int v){
        return f[u]<f[v];
    });
    // h[x]=1;
    for(auto y:out)dfs(y,x);
    int lim=f[x]+1;
    for(int s=0;s<(1<<(lim+1));s++){
        memset(d[s],0,sizeof(d[s]));
    }
    d[0][0]=1;
    for(auto y:out){
        for(int s=0;s<(1<<min(lim,f[y]+1));s++){
            memset(tg[s],0,sizeof(tg[s]));
        }
        for(int s=0;s<(1<<min(lim,f[y]+1));s++) {
            for(int j=0;j<=lim+1;j++){
                tg[s][j]=d[s][j]*h[y]%mod;
            }
        }
        for(int s=0;s<(1<<min(lim,f[y]+1));s++){
            for(int i=0;i<=min(f[y],lim);i++){
                if((s>>i)&1) continue;
                for(int j=0;j<=lim+1;j++){
                    (tg[s+(1<<i)][j]+=d[s][j]*dp[y][i])%=mod;
                }
                // for(int j=0;j<=lim+1;j++){
        // if(x==1&&s==0) cerr<<tg[0][1]<<endl;
                    (tg[s][i+1]+=d[s][0]*g[y][i])%=mod;    
                    // if(x==4&&s==0&&i==1){
                    //     cerr<<"?? "<<tg[s][i+1]<<" "<<d[s][0]<<" "<<g[y][i]<<endl;
                    // }
                // }
            }
        }
        for(int s=0;s<(1<<min(lim,f[y]+1));s++){
            memcpy(d[s],tg[s],sizeof(d[s]));
        }
    }
    for(int i=0;i<=lim;i++){
        dp[x][i]=d[(1<<i)-1][0];
        (h[x]+=dp[x][i])%=mod;
    }
    // cerr<<"??? "<<x<<" "<<g[2][0]<<"  "<<d[0][1]<<endl;
    // if(x==4) cerr<<"!!! "<<d[2][0]<<" "<<dp[1][1]<<endl;
    for(int i=0;i<=lim+1;i++){
        //j 空
        for(int j=0;j<i;j++){
            g[x][j]+=d[(1<<i)-(1<<j)-1][i+1];
    // if(x==4&&j==0) cerr<<i<<" "<<j<<" "<<d[(1<<i)-(1<<j)-1][i+1]<<" "<<d[0][2]<<" "<<g[1][1]<<endl;
        }
        for(int j=0;j<i;j++){
            (g[x][j]+=d[(1<<i)-(1<<j)-1][0])%=mod;
        }
        (h[x]+=d[(1<<i)-1][i+1])%=mod;
    }
}
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        v[x].push_back(y),v[y].push_back(x);
    }
    int rt=1;
    pfs(rt,0);
    dfs(rt,0);
    cerr<<g[4][0]<<" "<<g[1][1]<<endl;
    cout<<h[rt];
}
/*
3
1 2
2 3

5
1 2
1 3
1 4
4 5
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 10516kb

input:

6
1 2
5 4
6 5
3 1
1 5
3
6 1
2 3
6 4

output:

35

result:

wrong answer 1st lines differ - expected: '6 9 9 10 7 7', found: '35'