QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#321990#7607. The Doubling Game 2huazai676Compile Error//C++201.6kb2024-02-06 00:25:332024-02-06 00:25:34

Judging History

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

  • [2024-02-06 00:25:34]
  • 评测
  • [2024-02-06 00:25:33]
  • 提交

answer

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast","unroll-loops","inline","no-stack-protector")
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long ll;

const int N=3e5+10,mod=1e9+7;

int n,ans[N];
vector<int> T[N],f[N],g[N];

void add(int &x,ll y)
{
	x+=y%mod;
	if(x>=mod) x-=mod;
}

void dfs(int u,int fa)
{
	for(int v:T[u]) if(v!=fa) dfs(v,u);
	vector<int> f1(2),g1(2);
	f1[0]=1;
	int sz=0;
	sort(T[u].begin(),T[u].end(),[](int x,int y){return f[x].size()<f[y].size();});
	for(int v:T[u])
	{
		if(v==fa) continue;
		vector<int> f2(1<<(f[v].size())),g2(1<<(f[v].size()));
		for(int i=0;i<(1<<sz);i++)
		{
			add(f2[i],1LL*f1[i]*ans[v]),add(g2[i],1LL*g1[i]*ans[v]);
			for(int j=0;j<f[v].size();j++)
			{
				if((i>>j)&1) continue;
				add(f2[i|(1<<j)],1LL*f1[i]*f[v][j]);
				if((1<<j)>i) add(g2[i|(1<<j)],1LL*f1[i]*g[v][j]);
				else add(g2[i|(1<<j)],1LL*g1[i]*f[v][j]);
			}
		}
		swap(f1,f2),swap(g1,g2);
		sz=f[v].size();
		vector<int>().swap(f2),vector<int>().swap(g2);
	}
	f[u].resize(sz+1),g[u].resize(sz+1);
	for(int i=0;i<=sz;i++)
	{
		int s=(1<<i)-1;
		add(ans[u],f1[s]+g1[s]);
		add(f[u][i],f1[s]),add(g[u][i],f1[s]);
		for(int j=0;j<i-1;j++) add(g[u][j],f1[s^(1<<j)]+g1[s^(1<<j)]);
	}
//	while(!f[u].back()&&!g[u].back()) f[u].pop_back(),g[u].pop_back();
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		T[u].push_back(v),T[v].push_back(u);
	}
	dfs(1,0);
	cout<<ans[1];
	
	return 0;
}

Details

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bits/locale_classes.h:40,
                 from /usr/include/c++/13/bits/ios_base.h:41,
                 from /usr/include/c++/13/ios:44,
                 from /usr/include/c++/13/ostream:40,
                 from /usr/include/c++/13/iostream:41,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr 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’ ‘constexpr 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 answer.code:6:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~