oj.uz

Submission #634306

# Submission time Handle Problem Language Result Execution time Memory
634306 2022-08-24T08:48:43 Z S2speed Subtree (INOI20_subtree) C++17
0 / 100
 5 ms 5352 KB 
#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> gdj[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);
		gdj[v][u] = gdj[u][v] = true;
	}
	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();
	sub1();
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5352 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -