Submission #634321

#	Time	Username	Problem	Language	Result	Execution time	Memory
634321		S2speed	Subtree (INOI20_subtree)	C++17	20 / 100	78 ms	9940 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")

#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;

const ll maxn = 1e5 + 17 , md = 1e9 + 7 , inf = 2e16;

ll n , m;
ll dp[maxn];
vector<ll> adj[maxn];

void dDFS(ll r , ll par){
	ll h = 1;
	for(auto i : adj[r]){
		if(i == par) continue;
		dDFS(i , r);
		h *= dp[i] + 1; h %= md;
	}
	dp[r] = h;
	return;
}

void sub2(){
	for(ll i = 1 ; i < n ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		adj[v].push_back(u); adj[u].push_back(v);
	}
	dDFS(0 , -1);
	ll ans = 0;
	for(ll i = 0 ; i < n ; i++) ans += dp[i];
	ans %= md;
	cout<<ans<<'\n';
	return;
}

bitset<21> mark;
ll mask , cnt;

bool mDFS(ll r , ll par){
	mark[r] = true; cnt++;
	for(auto i : adj[r]){
		if(i == par) continue;
		if(mark[i]) return false;
		if(!(mask & (1 << i))) continue;
		if(!mDFS(i , r)) return false;
	}
	return true;
}

void sub1(){
	for(ll i = 0 ; i < m ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		adj[v].push_back(u); adj[u].push_back(v);
	}
	ll lm = (1 << n) , ans = 0;
	for(mask = 1 ; mask < lm ; mask++){
		cnt = 0;
		mark.reset();
		for(ll j = 0 ; j < n ; j++){
			if(mask & (1 << j)){
				if(mDFS(j , -1) && cnt == __builtin_popcount(mask)){
//					cout<<mask<<' ';
					ans++;
				}
				break;
			}
		}
	}
//	cout<<'\n';
	cout<<ans<<'\n';
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);

	cin>>n>>m;
	if(m == n - 1){
		sub2();
		return 0;
	}
	sub1();
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 0 / 30
• Subtask 4: 0 / 50