oj.uz

Submission #19744

# Submission time Handle Problem Language Result Execution time Memory
19744 2016-02-25T05:13:17 Z xdoju 트리 (kriii4_X) C++14
0 / 100
 0 ms 1212 KB 
#include <stdio.h>
#include <map>
#include <utility>
using namespace std;

const int MOD = 1000000007;

map<int, int> par;
map<int, int> cnt;

int getroot(int x){
  if(par.find(x) == par.end()) par[x] = x;
  if(par[x] == x) return x;

  return (par[x] = getroot(par[x]));
}

int mul(int x, int y){ return (long long)x * y % MOD; }

int power(int x, int y){
  if(y == 0) return 1;

  int r = power(x, y / 2);
  r = mul(r, r);
  if(y % 2 == 1) r = mul(r, x);
  return r;
}

int main(){
  int N, M; scanf("%d%d", &N, &M);

  bool val = true;

  for(int i = 1; i <= M; i++){
    int x, y; scanf("%d%d", &x, &y);

    int px = getroot(x), py = getroot(y);
    if(px == py) val = false;
    else par[px] = py;
  }

  if(!val){ puts("0"); }
  else{
    for(pair<int, int> pp : par){
      int x = pp.first;
      cnt[getroot(x)]++;
    }

    int NN = N - (int)par.size() + (int)cnt.size();

    int ans = 1;
    for(pair<int, int> pp : cnt) ans = mul(ans, pp.second);

    ans = mul(ans, power(N, NN - 2));

    printf("%d\n", ans);
  }
  return 0;
}

Subtask #1
0.0 / 9.0

# 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 Incorrect 0 ms 1212 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 -