| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19875 |
2016-02-25T06:30:05 Z |
tonyjjw |
트리 (kriii4_X) |
C++14 |
|
102 ms |
6244 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]);
}
bool merge(int a,int b){
if(getpar(a)==getpar(b))return true;
par[getpar(a)]=getpar(b);
return false;
}
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++){
if(merge(A[i],B[i]))return !printf("0\n");
}
if(M==N-1){
return !printf("1\n");
}
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;
}
//*/
| # |
Verdict |
Execution time |
Memory |
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 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 10 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 11 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 12 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 13 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 14 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 15 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 16 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 17 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 18 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 19 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 20 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 21 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 22 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 23 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 24 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 25 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 26 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 27 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 28 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 29 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 30 |
Correct |
0 ms |
4704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4836 KB |
Output is correct |
| 2 |
Correct |
21 ms |
5092 KB |
Output is correct |
| 3 |
Correct |
18 ms |
5092 KB |
Output is correct |
| 4 |
Correct |
9 ms |
4836 KB |
Output is correct |
| 5 |
Correct |
16 ms |
5092 KB |
Output is correct |
| 6 |
Correct |
95 ms |
6244 KB |
Output is correct |
| 7 |
Correct |
86 ms |
6244 KB |
Output is correct |
| 8 |
Correct |
66 ms |
6244 KB |
Output is correct |
| 9 |
Correct |
96 ms |
6244 KB |
Output is correct |
| 10 |
Correct |
77 ms |
6244 KB |
Output is correct |
| 11 |
Correct |
94 ms |
6244 KB |
Output is correct |
| 12 |
Correct |
86 ms |
6244 KB |
Output is correct |
| 13 |
Correct |
89 ms |
6244 KB |
Output is correct |
| 14 |
Correct |
88 ms |
6244 KB |
Output is correct |
| 15 |
Correct |
84 ms |
6244 KB |
Output is correct |
| 16 |
Correct |
97 ms |
6244 KB |
Output is correct |
| 17 |
Correct |
84 ms |
6244 KB |
Output is correct |
| 18 |
Correct |
0 ms |
4704 KB |
Output is correct |
| 19 |
Correct |
94 ms |
6244 KB |
Output is correct |
| 20 |
Correct |
98 ms |
6244 KB |
Output is correct |
| 21 |
Correct |
95 ms |
6244 KB |
Output is correct |
| 22 |
Correct |
88 ms |
6244 KB |
Output is correct |
| 23 |
Correct |
83 ms |
6244 KB |
Output is correct |
| 24 |
Correct |
82 ms |
6244 KB |
Output is correct |
| 25 |
Correct |
64 ms |
6244 KB |
Output is correct |
| 26 |
Correct |
59 ms |
6244 KB |
Output is correct |
| 27 |
Correct |
102 ms |
6244 KB |
Output is correct |
| 28 |
Correct |
101 ms |
6244 KB |
Output is correct |
| 29 |
Correct |
95 ms |
6244 KB |
Output is correct |
| 30 |
Correct |
95 ms |
6244 KB |
Output is correct |
