QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#282718 | #7607. The Doubling Game 2 | light_ink_dots | Compile Error | / | / | C++14 | 2.8kb | 2023-12-12 20:37:35 | 2023-12-12 20:37:35 |
Judging History
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 | } | ^