Submission #1184626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184626		8pete8	Star Trek (CEOI20_startrek)	C++20	85 / 100	54 ms	19016 KiB

startrek

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int32_t,int32_t>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e5,inf=1e18,minf=-1e18,lg=30,Mxn=1e9;
//#undef int
int n,k,m,d,q;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
int nim[mxn+10],nimu[mxn+10];
int nimr[mxn+10];

//rooted at, cur
vector<int>adj[mxn+10];

int mex(int c[2]){
	if(c[0]==0)return 0;
	return 1;
}
void dfs(int cur,int p){
	int c[2]={0,0};
	for(auto i:adj[cur]){
		if(i==p)continue;
		dfs(i,cur);
		c[!!nim[i]]++;
	}
	nim[cur]=mex(c);
}
void dfs2(int cur,int p){
	int c[2]={0,0};
	if(p!=-1)c[!!nimu[cur]]++;
	for(auto i:adj[cur])if(i!=p)c[!!nim[i]]++;
	nimr[cur]=mex(c);
	for(auto i:adj[cur])if(i!=p){
		c[!!nim[i]]--;
		nimu[i]=mex(c);
		c[!!nim[i]]++;
	}
	for(auto i:adj[cur])if(i!=p)dfs2(i,cur);
}
int C[mxn+10],Cu[mxn+10][2],Cr[mxn+10];
void dfs3(int cur,int p){
	int x=0;
	C[cur]+=(!nim[cur]);
	for(auto i:adj[cur])if(i!=p){
		dfs3(i,cur);
		x+=(!nim[i]);
	}
	if(x<=1){
		for(auto i:adj[cur])if(i!=p&&(nim[cur]^nim[i]))C[cur]+=C[i];
	}
}
void dfs4(int cur,int p){
	int x=0,sum=0;
	if(p!=-1)x+=(!nimu[cur]);
	for(auto i:adj[cur])if(i!=p){
		x+=(!nim[i]);
		Cu[cur][nim[i]]+=C[i];
	}
	Cr[cur]+=(!nimr[cur]);
	if(x<=1)Cr[cur]+=Cu[cur][!nimr[cur]];
	for(auto i:adj[cur])if(i!=p){
		x-=(!nim[i]);
		if(x<=1)Cu[i][x]+=(Cu[cur][!x]-((nim[i]!=x)?C[i]:0))+(!x);
		x+=(!nim[i]);
	}
	for(auto i:adj[cur])if(i!=p)dfs4(i,cur);
}
int cnt=0,D;
int binpow(int ex,int a){
	int ans=1;
	while(ex){
		if(ex&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		ex>>=1;
	}
	return ans;
}
int mul(int a,int b){return (a*b)%mod;}
int add(int a,int b){return (a+b+mod)%mod;}
mt19937 rng(time(NULL));
int dp[2];
int sum[2];
int get(int ex,int k){
	int x=(n*n),nex=(n*n)%mod,kex=k;
	int shift=0,ans=0;
	for(int i=0;i<=lg;i++){
		if(ex&(1LL<<i)){
			int tmp=x;
			tmp=mul(tmp,binpow(2*shift,n));
			ans=mul(ans,kex);
			ans=add(ans,tmp);
			shift+=(1LL<<i);
		}
		int a=x,b=x;
		b=mul(b,nex);
		a=mul(a,kex);
		x=add(a,b);
		nex=(nex*nex)%mod;
		kex=(kex*kex)%mod;
		if(shift==ex)break;
	}
	return ans;
}
int32_t main(){
	fastio
	cin>>n>>D;
	if(n==2){
		cout<<binpow(D,4);
		return 0;
	}
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	dfs(1,-1);
	dfs2(1,-1);
	dfs3(1,-1);
	dfs4(1,-1);

	for(int i=1;i<=n;i++){
		cnt+=nimr[i];
		sum[nimr[i]]=add(sum[nimr[i]],Cr[i]);
	}
	dp[1]=cnt;
	dp[0]=n-cnt;
	if(D==1){
		D--;
		if(nimr[1])cout<<add(mul(-Cr[1],dp[0]),mul(add(dp[0],dp[1]),n));
		else cout<<mul(Cr[1],dp[0]);
		return 0;
	}

	int k2=0;

	int k1=add(sum[1],-sum[0]);

	k2=get(D-2,k1);
	k2=mul(k2,mul(mul(n,add(n,-cnt)),binpow(mod-2,n)));
	dp[0]=add(mul(n-cnt,binpow(D-2,k1)),k2); 

	dp[1]=add(mul(dp[0],add(sum[0],-sum[1])),mul(binpow(2*D-3,n),mul(n,cnt)));
	dp[0]=add(mul(dp[0],add(sum[1],-sum[0])),mul(binpow(2*D-3,n),mul(n,add(n,-cnt))));
	if(nimr[1])cout<<add(mul(-Cr[1],dp[0]),mul(add(dp[0],dp[1]),n));
	else cout<<mul(Cr[1],dp[0]);
}
/*
   
*/

Compilation message (stderr)

startrek.cpp:16:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   16 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
startrek.cpp:23:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   23 | void setIO(string name){
      |                       ^
startrek.cpp:34:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   34 | int mex(int c[2]){
      |                 ^
startrek.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void dfs(int cur,int p){
      |                       ^
startrek.cpp:47:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   47 | void dfs2(int cur,int p){
      |                        ^
startrek.cpp:60:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   60 | void dfs3(int cur,int p){
      |                        ^
startrek.cpp:71:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   71 | void dfs4(int cur,int p){
      |                        ^
startrek.cpp:88:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   88 | int binpow(int ex,int a){
      |                        ^
startrek.cpp:97:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   97 | int mul(int a,int b){return (a*b)%mod;}
      |                    ^
startrek.cpp:98:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   98 | int add(int a,int b){return (a+b+mod)%mod;}
      |                    ^
startrek.cpp:102:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  102 | int get(int ex,int k){
      |                     ^
startrek.cpp:123:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  123 | int32_t main(){
      |              ^
startrek.cpp: In function 'void setIO(std::string)':
startrek.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
startrek.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 0 / 15