| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 18993 |
2016-02-17T02:48:15 Z |
kriii |
트리 (kriii4_X) |
C++14 |
|
0 ms |
1208 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()
{
freopen ("input.txt","r",stdin);
freopen ("output.txt","w",stdout);
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1208 KB |
open (syscall #2) was called by the program (disallowed syscall) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
