Submission #173479

#	Time	Username	Problem	Language	Result	Execution time	Memory
173479		jhwest2	우호 조약 체결 (JOI14_friends)	C++14	100 / 100	296 ms	11384 KiB

friends

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N, M;
int par[100010], size[100010];
vector<int> E[100010];

int Find(int a) {
	if (par[a] == a) return a;
	return par[a] = Find(par[a]);
}
void Union(int a, int b) {
	if (Find(a) == Find(b)) return;
	size[Find(a)] += size[Find(b)];
	par[Find(b)] = Find(a);
}
void dfs(int key, int cur) {
	Union(key, cur);
	for (int nxt : E[cur]) {
		if (Find(nxt) == Find(cur)) continue;
		dfs(key, nxt);
	}
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> N >> M;
	for (int i=0; i<M; i++) {
		int x, y; cin >> x >> y;
		E[x].push_back(y);
	}

	for (int i=1; i<=N; i++) par[i] = i, size[i] = 1;
	for (int i=1; i<=N; i++) {
		if (E[i].size() >= 2) {
			for (int j=1; j<E[i].size(); j++) {
				Union(E[i][0], E[i][j]);
				dfs(E[i][0], E[i][0]);
				dfs(E[i][j], E[i][j]);
			}
		}
	}

	ll ans = 0;
	for (int i=1; i<=N; i++) {
		if (Find(i) != i) continue;
		ans += (ll)size[i] * (size[i]-1);
	}

	for (int i=1; i<=N; i++) {
		for (int edge : E[i]) {
			if (Find(i) != Find(edge)) ++ans;
		}
	}
	cout << ans;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j=1; j<E[i].size(); j++) {
                  ~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65