oj.uz

Submission #19929

# Submission time Handle Problem Language Result Execution time Memory
19929 2016-02-25T07:21:58 Z Namnamseo 트리 (kriii4_X) C++14
0 / 100
 0 ms 2972 KB 
#include <cstdio>
#include <map>
using namespace std;
map<int,int> vv;
int par [200010], vind;
int size[200010];
bool chk[200010];
int n,m;
inline int conv(int x){
    int& ret=vv[x];
    if(ret==0){
        ++vind;
        par [vind]=vind;
        size[vind]=1;
        ret=vind;
    }
    return ret;
}
int root(int x){ return (x==par[x])?x:(par[x]=root(par[x])); }
const int M=int(1e9)+7;
long long pow(long long x,long long y){
    if(y==0)return 1;
    if(y==1)return x;
    long long o=pow(x,y/2);
    if(y%2==0)return o*o%M;
    else return o*o%M*x%M;
}
int main()
{
    scanf("%d%d",&n,&m);
    int i,a,b;
    for(i=0;i<m;++i){
        scanf("%d%d",&a,&b);
        a=root(conv(a)); b=root(conv(b));
        if(a==b){
            puts("0"); return 0;
        }
        par [a]=b;
        size[b]+=size[a];
    }
    int allmul=1;
    for(i=1; i<=vind; ++i){
        a=root(i);
        if(chk[a]) continue;
        chk[a]=true;
        allmul=(allmul*1LL*size[a])%M;
    }
    if(n==m+1){
        printf("%d\n",n);
    } else printf("%d\n",int( pow(n, n-m-2) * allmul % M ));
    return 0;
}

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2972 KB Output is correct
2 Correct 0 ms 2972 KB Output is correct
3 Correct 0 ms 2972 KB Output is correct
4 Correct 0 ms 2972 KB Output is correct
5 Correct 0 ms 2972 KB Output is correct
6 Correct 0 ms 2972 KB Output is correct
7 Correct 0 ms 2972 KB Output is correct
8 Correct 0 ms 2972 KB Output is correct
9 Incorrect 0 ms 2972 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 91.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -