QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#282718#7607. The Doubling Game 2light_ink_dotsCompile Error//C++142.8kb2023-12-12 20:37:352023-12-12 20:37:35

Judging History

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

  • [2023-12-12 20:37:35]
  • 评测
  • [2023-12-12 20:37:35]
  • 提交

answer

#include<iostream>
#include<cstring>
#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];
    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;    
                // }
            }
        }
        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;
    }
    // if(x==1) cerr<<h[x]<<" "<<d[1][2]<<" "<<d[0][1]<<" "<<g[2][0]<<endl;
    // cerr<<"??? "<<x<<" "<<g[2][0]<<"  "<<d[0][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];
        }
        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<<"????? "<<f[1]<<" "<<h[2]<<" "<<g[2][1]<<" "<<g[2][0]<<endl;
    cout<<h[rt];
}
/*
3
1 2
2 3

5
1 2
1 3
1 4
4 5
*/

Details

answer.code:9:1: error: ‘vector’ does not name a type
    9 | vector<int>v[N];
      | ^~~~~~
answer.code:12:15: error: ‘vector’ does not name a type
   12 | int mex(const vector<int>&a){
      |               ^~~~~~
answer.code:12:21: error: expected ‘,’ or ‘...’ before ‘<’ token
   12 | int mex(const vector<int>&a){
      |                     ^
answer.code: In function ‘long long int mex(int)’:
answer.code:15:15: error: ‘a’ was not declared in this scope
   15 |     for(int x:a)
      |               ^
answer.code: In function ‘void pfs(long long int, long long int)’:
answer.code:24:5: error: ‘vector’ was not declared in this scope
   24 |     vector<int>s;
      |     ^~~~~~
answer.code:4:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    3 | #include<algorithm>
  +++ |+#include <vector>
    4 | using namespace std;
answer.code:7:13: error: expected primary-expression before ‘long’
    7 | #define int long long
      |             ^~~~
answer.code:24:12: note: in expansion of macro ‘int’
   24 |     vector<int>s;
      |            ^~~
answer.code:25:16: error: ‘v’ was not declared in this scope
   25 |     for(auto y:v[x]){
      |                ^
answer.code:28:9: error: ‘s’ was not declared in this scope
   28 |         s.push_back(f[y]);
      |         ^
answer.code:30:14: error: ‘s’ was not declared in this scope
   30 |     f[x]=mex(s);
      |              ^
answer.code: In function ‘void dfs(long long int, long long int)’:
answer.code:35:5: error: ‘vector’ was not declared in this scope
   35 |     vector<int>out;
      |     ^~~~~~
answer.code:35:5: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
answer.code:7:13: error: expected primary-expression before ‘long’
    7 | #define int long long
      |             ^~~~
answer.code:35:12: note: in expansion of macro ‘int’
   35 |     vector<int>out;
      |            ^~~
answer.code:36:15: error: ‘v’ was not declared in this scope
   36 |     for(int y:v[x]) if(y!=fa) out.push_back(y);
      |               ^
answer.code:36:31: error: ‘out’ was not declared in this scope
   36 |     for(int y:v[x]) if(y!=fa) out.push_back(y);
      |                               ^~~
answer.code:37:10: error: ‘out’ was not declared in this scope
   37 |     sort(out.begin(),out.end(),[&](int u,int v){
      |          ^~~
answer.code: In function ‘int32_t main()’:
answer.code:94:9: error: ‘v’ was not declared in this scope
   94 |         v[x].push_back(y),v[y].push_back(x);
      |         ^
answer.code: In function ‘long long int mex(int)’:
answer.code:22:1: warning: control reaches end of non-void function [-Wreturn-type]
   22 | }
      | ^