oj.uz

Submission #18994

# Submission time Handle Problem Language Result Execution time Memory
18994 2016-02-17T02:48:37 Z kriii 트리 (kriii4_X) C++14
100 / 100
 526 ms 25636 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Correct 0 ms 1216 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct
4 Correct 0 ms 1216 KB Output is correct
5 Correct 0 ms 1216 KB Output is correct
6 Correct 0 ms 1216 KB Output is correct
7 Correct 0 ms 1216 KB Output is correct
8 Correct 0 ms 1216 KB Output is correct
9 Correct 0 ms 1216 KB Output is correct
10 Correct 0 ms 1216 KB Output is correct
11 Correct 0 ms 1216 KB Output is correct
12 Correct 0 ms 1216 KB Output is correct
13 Correct 0 ms 1216 KB Output is correct
14 Correct 0 ms 1216 KB Output is correct
15 Correct 0 ms 1216 KB Output is correct
16 Correct 0 ms 1216 KB Output is correct
17 Correct 0 ms 1216 KB Output is correct
18 Correct 0 ms 1216 KB Output is correct
19 Correct 0 ms 1216 KB Output is correct
20 Correct 0 ms 1216 KB Output is correct
21 Correct 0 ms 1216 KB Output is correct
22 Correct 0 ms 1216 KB Output is correct
23 Correct 0 ms 1216 KB Output is correct
24 Correct 0 ms 1216 KB Output is correct
25 Correct 0 ms 1216 KB Output is correct
26 Correct 0 ms 1216 KB Output is correct
27 Correct 0 ms 1216 KB Output is correct
28 Correct 0 ms 1216 KB Output is correct
29 Correct 0 ms 1216 KB Output is correct
30 Correct 0 ms 1216 KB Output is correct

Subtask #2
91.0 / 91.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3592 KB Output is correct
2 Correct 100 ms 6100 KB Output is correct
3 Correct 102 ms 6496 KB Output is correct
4 Correct 35 ms 3328 KB Output is correct
5 Correct 62 ms 5044 KB Output is correct
6 Correct 495 ms 24976 KB Output is correct
7 Correct 485 ms 25372 KB Output is correct
8 Correct 100 ms 7288 KB Output is correct
9 Correct 505 ms 25636 KB Output is correct
10 Correct 505 ms 23920 KB Output is correct
11 Correct 473 ms 19036 KB Output is correct
12 Correct 475 ms 18772 KB Output is correct
13 Correct 480 ms 18904 KB Output is correct
14 Correct 508 ms 18904 KB Output is correct
15 Correct 495 ms 19168 KB Output is correct
16 Correct 492 ms 19432 KB Output is correct
17 Correct 482 ms 19432 KB Output is correct
18 Correct 0 ms 1216 KB Output is correct
19 Correct 510 ms 19828 KB Output is correct
20 Correct 526 ms 19828 KB Output is correct
21 Correct 479 ms 18772 KB Output is correct
22 Correct 489 ms 19300 KB Output is correct
23 Correct 480 ms 19696 KB Output is correct
24 Correct 500 ms 19696 KB Output is correct
25 Correct 323 ms 17188 KB Output is correct
26 Correct 339 ms 17188 KB Output is correct
27 Correct 506 ms 23656 KB Output is correct
28 Correct 506 ms 23656 KB Output is correct
29 Correct 507 ms 19960 KB Output is correct
30 Correct 495 ms 19960 KB Output is correct