Submission #1182705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182705		8pete8	Star Trek (CEOI20_startrek)	C++20	45 / 100	150 ms	20828 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];
struct fen{
	int fwk[mxn+10];
	void update(int pos,int val){
		pos++;
		for(int i=pos;i<=n;i+=(i&-i))fwk[i]+=val;
	}
	int qry(int pos){
		pos++;
		int sum=0;
		for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
		return sum;
	}
	int get(){
		int pos=0,sum=0;
		for(int i=lg;i>=0;i--)if(pos+(1LL<<i)<=n&&(sum+fwk[i+(1LL<<i)]==pos+(1LL<<i))){
			pos+=(1LL<<i);
			sum+=fwk[pos];
		}
		return pos;
	}
}t;
int mex(vector<int>have){
	sort(all(have));
	for(int i=0;i<have.size();i++){
		if(i==0||have[i-1]!=have[i])t.update(have[i],1);
	}
	int x=t.get();
	for(int i=0;i<have.size();i++){
		if(i==0||have[i-1]!=have[i])t.update(have[i],-1);
	}
	return x;
}
void dfs(int cur,int p){
	vector<int>have;
	for(auto i:adj[cur]){
		if(i==p)continue;
		dfs(i,cur);
		have.pb(nim[i]);
	}
	nim[cur]=mex(have);
}

int C[mxn+10];
void add(int x){
	if(!C[x])t.update(x,1);
	C[x]++;
}
void del(int x){
	C[x]--;
	if(!C[x])t.update(x,-1);
}
void dfs2(int cur,int p){
	if(p!=-1)add(nimu[cur]);
	for(auto i:adj[cur])if(i!=p)add(nim[i]);
	nimr[cur]=t.get();
	for(auto i:adj[cur])if(i!=p){
		if(C[nim[i]]==1)del(nim[i]);
		nimu[i]=t.get();
		if(!C[nim[i]])add(nim[i]);
	}
	for(auto i:adj[cur])if(i!=p)del(nim[i]);
	if(p!=-1)del(nimu[cur]);

	for(auto i:adj[cur])if(i!=p)dfs2(i,cur);
}


int D,cnt=0,ans=0;
void getans(int cur,int p,int dept,int yes){
	if(dept%2){
		//cnt 1
		for(auto i:adj[cur])if(i!=p)getans(i,cur,dept+1,yes);
		if(!yes)ans=(ans+cnt)%mod;
		else ans=(ans+n)%mod;
	}
	else{
		int x=0;
		//cnt 0
		for(auto i:adj[cur])if(i!=p)x+=(!nim[i]);
		for(auto i:adj[cur])if(i!=p){
			if(nim[i])getans(i,cur,dept+1,1);
			else getans(i,cur,dept+1,(yes||x>1));
		}
		ans=(ans+n)%mod;
	}
}
void getans2(int cur,int p,int dept,int yes){
	if(yes)return;
	if(dept%2){
		//cnt 1
		int x=0;
		for(auto i:adj[cur])if(i!=p)x+=(!nim[i]);
		for(auto i:adj[cur])if(i!=p){
			if(nim[i])getans2(i,cur,dept+1,1);
			else getans2(i,cur,dept+1,(yes|x>1));
		}
	}
	else{
		if(!yes)ans=(ans+n-cnt+mod)%mod;
		for(auto i:adj[cur])if(i!=p)getans2(i,cur,dept+1,yes);
	}
}
int pow(int ex){
	int ans=1,a=4;
	while(ex){
		if(ex&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		ex>>=1;
	}
	return ans;
}
int32_t main(){
	fastio
	cin>>n>>D;
	if(n==2){
		cout<<pow(D);
		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);
	for(int i=1;i<=n;i++)if(nimr[i])cnt++;
	if(nim[1])getans(1,1,0,0);
	else getans2(1,1,0,0);
	cout<<ans;
}

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:35:36: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   35 |         void update(int pos,int val){
      |                                    ^
startrek.cpp:39:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 |         int qry(int pos){
      |                        ^
startrek.cpp:45:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   45 |         int get(){
      |                 ^
startrek.cpp:54:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   54 | int mex(vector<int>have){
      |                        ^
startrek.cpp:65:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   65 | void dfs(int cur,int p){
      |                       ^
startrek.cpp:76:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   76 | void add(int x){
      |               ^
startrek.cpp:80:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   80 | void del(int x){
      |               ^
startrek.cpp:84:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   84 | void dfs2(int cur,int p){
      |                        ^
startrek.cpp:101:43: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  101 | void getans(int cur,int p,int dept,int yes){
      |                                           ^
startrek.cpp:119:44: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  119 | void getans2(int cur,int p,int dept,int yes){
      |                                            ^
startrek.cpp:135:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  135 | int pow(int ex){
      |               ^
startrek.cpp:144:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  144 | 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: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15