Submission #19864

#	Time	Username	Problem	Language	Result	Execution time	Memory
19864		cki86201	트리 (kriii4_X)	C++14	100 / 100	189 ms	11592 KiB

X

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

const ll MOD = 1e9 + 7;

ll pw(ll x, ll y){
	ll res = 1;
	while(y){
		if(y & 1)res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}

map <int, int> M;
int cn;
int par[200020], w[200020];
int Find(int x){return par[x] == x ? x : par[x] = Find(par[x]);}
int q[100010][2];

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	rep(i, m){
		int x, y;
		scanf("%d%d", &x, &y);
		if(M.find(x) == M.end())M[x] = ++cn;
		if(M.find(y) == M.end())M[y] = ++cn;
		q[i][0] = M[x], q[i][1] = M[y];
	}
	for(int i=1;i<=cn;i++)par[i] = i, w[i] = 1;
	int ok = 1;
	for(int i=0;i<m;i++){
		int a = q[i][0], b = q[i][1];
		a = Find(a), b = Find(b);
		if(a == b){
			ok = 0;
			break;
		}
		par[a] = b;
		w[b] += w[a];
	}
	if(!ok){
		printf("0");
		return 0;
	}
	else{
		ll ans = 1, sum = n - cn;
		int cnt = n - cn;
		for(int i=1;i<=cn;i++){
			if(Find(i) == i){
				ans = ans * w[i] % MOD;
				sum = (sum + w[i]) % MOD;
				cnt++;
			}
		}
		if(cnt > 1)ans = ans * pw(sum, cnt-2) % MOD;
		else ans = 1;
		printf("%lld", ans);
	}
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 91 / 91