Submission #18973

#	Time	Username	Problem	Language	Result	Execution time	Memory
18973		tncks0121	트리 (kriii4_X)	C++14	100 / 100	155 ms	11080 KiB

X

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
#include <functional>
#include <numeric>
#include <iostream>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

#define debug(format, ...) printf(format, __VA_ARGS__);

const int N_ = (int)1e9 + 10;
const int M_ = (int)1e5 + 10;

const ll MOD = (ll)1e9 + 7;

ll modpow (ll a, ll b) {
	a %= MOD;
	ll ret = 1;
	while(b > 0) {
		if(b & 1) ret = (ret * a) % MOD;
		a = (a * a) % MOD;
		b >>= 1;
	}
	return ret;
}

struct mint {
	ll val;
	mint(ll val = 0): val((val % MOD + MOD) % MOD) { }
	mint operator+(mint p) { return val + p.val; }
	mint operator-(mint p) { return val - p.val; }
	mint operator*(mint p) { return val * p.val; }
	mint operator/(mint p) { return val * modpow(p.val, MOD-2); }
};

int N, M;

unordered_map<int, int> grp, sz;

int get_grp (int x) {
	if(grp.count(x) == 0) grp[x] = x, sz[x] = 1;
	if(grp[x] == x) return x;
	return grp[x] = get_grp(grp[x]);
}

int deg[100];
int tmp[100];

void brute (int x, int sum) {
	if(x > N-M) {
		for(int i =1; i<= N-M;i++) printf("%d ", tmp[i]+1);
		puts("");
		return;
	}
	for(int cur = 0; cur + sum <= N-M-2; cur++) {
		if(x == N-M) cur = N-M-2-sum;
		tmp[x] = cur;
		brute(x+1, sum+cur);
		tmp[x] = 0;
	}
}

int main() {
	scanf("%d%d", &N, &M);
	for(int i = 0; i < M; i++) {
		int u, v; scanf("%d%d", &u, &v);

		int a = get_grp(u);
		int b = get_grp(v);
		if(a == b)
			return 0 & puts("0");

		if(rand() & 1) swap(a, b);
		grp[a] = b;
		sz[b] += sz[a];
		sz.erase(a);
	}

	mint ans;

	if(M == N-1) {
		ans = 1;
	}else {
		ans = modpow(N, N - M - 2);
		for(auto it : sz) ans = ans * it.second;	
	}

	printf("%lld\n", ans.val);
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 91 / 91