oj.uz

답안 #19853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19853 2016-02-25T06:18:43 Z tonyjjw 트리 (kriii4_X) C++14
0 / 100
 0 ms 4704 KB 
//*
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<vector>
#define all(A) (A).begin(), (A).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int MM = 200000;
const ll mod = 1000000007;

ll N;
int M;
int A[MM],B[MM];
int par[MM];
int cnt[MM];
int nN;

int getpar(int n){
	if(par[n]==n)return n;
	return par[n]=getpar(par[n]);
}

void merge(int a,int b){
	par[getpar(a)]=getpar(b);
}

ll mpow(ll a,ll p){
	ll r=1;
	while(p>0){
		if(p&1)r=r*a%mod;
		a=a*a%mod;
		p>>=1;
	}
	return r;
}

int main(){
	scanf("%lld%d",&N,&M);
	vector<int> nodes;
	for(int i=0;i<M;i++){
		scanf("%d%d",&A[i],&B[i]);
		nodes.push_back(A[i]),nodes.push_back(B[i]);
	}
	sort(all(nodes));
	nodes.resize(unique(all(nodes))-nodes.begin());
	for(int i=0;i<M;i++){
		A[i]=lower_bound(all(nodes),A[i])-nodes.begin();
		B[i]=lower_bound(all(nodes),B[i])-nodes.begin();
	}
	nN=nodes.size();
	for(int i=0;i<nN;i++)par[i]=i;
	for(int i=0;i<M;i++){
		merge(A[i],B[i]);
	}
	for(int i=0;i<nN;i++){
		cnt[getpar(i)]++;
	}
	ll ans=mpow(N,N-M-2);
	for(int i=0;i<nN;i++)if(par[i]==i){
		ans*=cnt[i];
		ans%=mod;
	}
	printf("%lld\n",ans);
	return 0;
}
//*/

Subtask #1
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 4704 KB Output is correct
2 Correct 0 ms 4704 KB Output is correct
3 Correct 0 ms 4704 KB Output is correct
4 Correct 0 ms 4704 KB Output is correct
5 Correct 0 ms 4704 KB Output is correct
6 Correct 0 ms 4704 KB Output is correct
7 Correct 0 ms 4704 KB Output is correct
8 Correct 0 ms 4704 KB Output is correct
9 Incorrect 0 ms 4704 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 91.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -