| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19887 |
2016-02-25T06:45:22 Z |
gs13068 |
트리 (kriii4_X) |
C++ |
|
640 ms |
16260 KB |
#include <cstdio>
#include <map>
const int p = 1000000007;
using namespace std;
int pw(int x, int y)
{
return y & 1 ? (long long)pw(x, y ^ 1)*x%p : y ? pw((long long)x*x%p, y >> 1) : 1;
}
map<int, int> M, S;
int f(int x)
{
if (M.find(x) == M.end()) M[x] = x;
int t = M[x];
return x == t ? x : M[x] = f(t);
}
void g(int x, int y)
{
x = f(x);
y = f(y);
if (S.find(x) == S.end()) S[x] = 1;
if (S.find(y) == S.end()) S[y] = 1;
S[x] += S[y];
M[y] = M[x];
}
int main()
{
map<int, int>::iterator it;
int i, j, k, n, m, r;
scanf("%d%d", &n, &m);
for (k = 0; k < m;k++)
{
scanf("%d%d", &i, &j);
if (f(i) == f(j))
{
puts("0");
return 0;
}
g(i, j);
}
if (m == n - 1)
{
puts("1");
return 0;
}
r = pw(n, n - m - 2);
for (it = S.begin(); it != S.end(); it++) if (it->first == f(it->first)) r = (long long)r * it->second % p;
printf("%d", r);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 21 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 23 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 25 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 26 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 27 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 28 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 29 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 30 |
Correct |
0 ms |
1212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
2400 KB |
Output is correct |
| 2 |
Correct |
126 ms |
3588 KB |
Output is correct |
| 3 |
Correct |
129 ms |
3852 KB |
Output is correct |
| 4 |
Correct |
43 ms |
2268 KB |
Output is correct |
| 5 |
Correct |
86 ms |
3192 KB |
Output is correct |
| 6 |
Correct |
587 ms |
15600 KB |
Output is correct |
| 7 |
Correct |
593 ms |
15864 KB |
Output is correct |
| 8 |
Correct |
103 ms |
4776 KB |
Output is correct |
| 9 |
Correct |
576 ms |
16260 KB |
Output is correct |
| 10 |
Correct |
591 ms |
14544 KB |
Output is correct |
| 11 |
Correct |
577 ms |
10056 KB |
Output is correct |
| 12 |
Correct |
558 ms |
9924 KB |
Output is correct |
| 13 |
Correct |
570 ms |
10056 KB |
Output is correct |
| 14 |
Correct |
565 ms |
10056 KB |
Output is correct |
| 15 |
Correct |
571 ms |
10188 KB |
Output is correct |
| 16 |
Correct |
466 ms |
10320 KB |
Output is correct |
| 17 |
Correct |
460 ms |
10320 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 19 |
Correct |
626 ms |
10452 KB |
Output is correct |
| 20 |
Correct |
616 ms |
10452 KB |
Output is correct |
| 21 |
Correct |
566 ms |
9924 KB |
Output is correct |
| 22 |
Correct |
577 ms |
10188 KB |
Output is correct |
| 23 |
Correct |
603 ms |
10584 KB |
Output is correct |
| 24 |
Correct |
612 ms |
10452 KB |
Output is correct |
| 25 |
Correct |
383 ms |
10584 KB |
Output is correct |
| 26 |
Correct |
372 ms |
10584 KB |
Output is correct |
| 27 |
Correct |
584 ms |
14280 KB |
Output is correct |
| 28 |
Correct |
566 ms |
14280 KB |
Output is correct |
| 29 |
Correct |
614 ms |
10584 KB |
Output is correct |
| 30 |
Correct |
640 ms |
10584 KB |
Output is correct |
