Submission #18994

#	Time	Username	Problem	Language	Result	Execution time	Memory
18994		kriii	트리 (kriii4_X)	C++14	100 / 100	526 ms	25636 KiB

X

#include <stdio.h>
#include <map>
#include <set>
using namespace std;

const long long mod = 1000000007;

long long fpow(long long a, long long p)
{
	long long r = 1;
	while (p){
		if (p & 1) r = r * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return r;
}

map<int, int> par,sz;

int find(int x)
{
	bool good = par.count(x);
	int &p = par[x];
	if (!good){
		p = x;
		sz[x] = 1;
	}
	else{
		if (x != p) p = find(p);
	}
	return p;
}

int main()
{
	int N,M; scanf ("%d %d",&N,&M);
	if (N < 1) fprintf (stderr,"N low\n");
	if (N > 1000000000) fprintf (stderr,"N high\n");
	if (M < 0) fprintf (stderr,"M low\n");
	if (M > 100000) fprintf (stderr,"M high\n");

	int comp = N;
	set<pair<int, int> > chk;
	for (int i=0;i<M;i++){
		int x,y; scanf ("%d %d",&x,&y);
		if (x < 1) fprintf (stderr,"x low\n");
		if (x > N) fprintf (stderr,"x high\n");
		if (y < 1) fprintf (stderr,"y low\n");
		if (y > N) fprintf (stderr,"y high\n");
		if (x == y) fprintf (stderr,"x==y\n");
		if (chk.count(make_pair(x,y))) fprintf (stderr,"duplicated\n");
		chk.insert(make_pair(x,y));
		chk.insert(make_pair(y,x));
		x = find(x); y = find(y);
		if (x != y){
			par[x] = y;
			sz[y] += sz[x];
			comp--;
		}
		else{
			puts("0");
			return 0;
		}
	}

	long long ans = 1;
	if (comp > 1){
		for (auto &p : par) if (p.first == p.second) ans = ans * sz[p.first] % mod;
		ans = ans * fpow(N,comp-2) % mod;
	}
	
	printf ("%lld\n",ans);

	return 0;
}

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