QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404770#7607. The Doubling Game 2ucup-team3396#Compile Error//C++142.4kb2024-05-04 17:52:202024-05-04 17:52:20

Judging History

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

  • [2024-05-04 17:52:20]
  • 评测
  • [2024-05-04 17:52:20]
  • 提交

answer

#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
#pragma GCC target("avx")
#include <bits/stdc++.h>
#define double long double
#define lowbit(i) (i&(-i))
#define mid ((l+r)>>1)
#define add(i,j) (((i+j)>=mod)?i+j-mod:i+j)
using namespace std;
const int mod=1e9+7;
int siz[300005];
vector<int> vc[300005];
int cnt[300005];
int dp[300005][35][3];
int f[1200005][2],g[1200005][2];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void dfs(int now,int fa){
	for(auto v:vc[now]){
		if(v==fa) continue;
		dfs(v,now);
	}
	for(auto v:vc[now]) if(v!=fa) cnt[siz[v]]++;
	for(int i=20;i>=0;--i) cnt[i]+=cnt[i+1];
	for(int i=20;i>=0;--i){
		bool ok=1;
		for(int j=0;j<i;++j){
			if(cnt[j]<i-j) ok=0;
		}
		if(ok){
			siz[now]=i;
			break;
		}
	}
	for(int i=0;i<=20;++i) cnt[i]=0;
	for(int i=0;i<(1<<(siz[now]+2));++i) f[i][0]=f[i][1]=0;
	f[0][0]=1;
	for(auto v:vc[now]){
		if(v==fa) continue;
		for(int i=0;i<(1<<(siz[now]+2));++i) g[i][0]=g[i][1]=0;
		int tot=0;
		for(int j=0;j<=siz[v];++j) (tot+=dp[v][j][0]+dp[v][j][2])%=mod;
		for(int j=0;j<=min(siz[v],siz[now]);++j){
			for(int i=0;i<(1<<(siz[now]+2));++i){
				if(!((i>>j)&1)){
					g[i|(1<<j)][0]=add(g[i|(1<<j)][0],1ll*f[i][0]*dp[v][j][0]%mod);
					if((1<<j)<i) g[i|(1<<j)][1]=add(g[i|(1<<j)][1],1ll*f[i][1]*dp[v][j][0]%mod);
					if((1<<j)>i) g[i|(1<<j)][1]=add(g[i|(1<<j)][1],1ll*f[i][0]*dp[v][j][1]%mod);
				}
			}
		}
		for(int i=0;i<(1<<(siz[now]+2));++i) f[i][0]=(1ll*f[i][0]*tot+g[i][0])%mod,f[i][1]=(1ll*f[i][1]*tot+g[i][1])%mod;
	}
	for(int i=0;i<=siz[now];++i){
		dp[now][i][0]=f[(1<<i)-1][0];
		dp[now][i][2]=f[(1<<i)-1+(1<<i)][1];
	}
	for(int i=0;i<=siz[now]+1;++i){
		for(int j=0;j<i;++j){
			dp[now][j][1]=add(dp[now][j][1],add(f[(1<<i)-1-(1<<j)][0],f[(1<<i)-1-(1<<j)+(1<<i)][1]));
//			if(now==4&&i==1&&j==0) cout<<"OK"<<f[(1<<i)-1-(1<<j)][0]<<" "<<f[(1<<i)-1-(1<<j)+(1<<i)][1]<<" "<<dp[now][j][1]<<" ";
		}
	}
//	cout<<now<<" "<<siz[now]<<"\n";
//	for(int i=0;i<=siz[now]+1;i++) cout<<dp[now][i][0]<<" "<<dp[now][i][1]<<" "<<dp[now][i][2]<<"\n";
}
signed main(){
	int n; n=read();
	for(int i=1;i<n;i++){
		int u,v; u=read(),v=read();
		vc[u].emplace_back(v);
		vc[v].emplace_back(u);
	}
	dfs(1,0);
	int ans=0;
	for(int i=0;i<=siz[1];++i) (ans+=dp[1][i][0]+dp[1][i][2]);
	cout<<ans%mod;
	return 0;
}

Details

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/queue:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:157:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~