Submission #21416

#	Time	Username	Problem	Language	Result	Execution time	Memory
21416		gs14004	트리 (kriii4_X)	C++11	100 / 100	116 ms	5988 KiB

X

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

const int MAXN = 200005;
struct disj{
	int pa[MAXN], sz[MAXN];
	void init(int n){
		for(int i=0; i<=n; i++){
			pa[i] = i;
			sz[i] = 1;
		}
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p;
		sz[p] += sz[q];
		return 1;
	}
}disj;

int n, m;
pi e[100005];
vector<int> v;

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++){
		scanf("%d %d",&e[i].first, &e[i].second);
		v.push_back(e[i].first);
		v.push_back(e[i].second);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	disj.init(v.size());
	for(int i=0; i<m; i++){
		e[i].first = lower_bound(v.begin(), v.end(), e[i].first) - v.begin();
		e[i].second = lower_bound(v.begin(), v.end(), e[i].second) - v.begin();
		if(!disj.uni(e[i].first, e[i].second)){
			puts("0");
			return 0;
		}
	}
	if(n - 1 == m){
		puts("1");
		return 0;
	}
	lint ans = ipow(n, n - m - 2);
	for(int i=0; i<v.size(); i++){
		if(disj.find(i) == i){
			ans *= disj.sz[i];
			ans %= mod;
		}
	}
	cout << ans;
}

Compilation message (stderr)

X.cpp: In function 'int main()':
X.cpp:68:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
                ^
X.cpp:46:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
X.cpp:48:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&e[i].first, &e[i].second);
                                           ^

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