QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#282720 | #7610. Bus Lines | light_ink_dots | WA | 4ms | 10516kb | C++14 | 3.0kb | 2023-12-12 20:57:59 | 2023-12-12 20:58:00 |
Judging History
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'