Submission #1186137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186137		JooDdae	우호 조약 체결 (JOI14_friends)	C++20	100 / 100	49 ms	8008 KiB

friends

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, p[100100], s[100100], chk[100100];
vector<int> v[100100];
queue<int> q;

int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }

void merge(int x, int y) { 
	if((x = find(x)) == (y = find(y))) return;
	p[x] = y, s[y] += s[x];
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i=1;i<=m;i++) {
		int x, y; cin >> x >> y;
		v[x].push_back(y);
	}

	iota(p, p+1+n, 0), fill(s, s+1+n, 1);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<v[i].size();j++) {
			merge(v[i][j-1], v[i][j]);
		}
	}

	for(int i=1;i<=n;i++) if(s[find(i)] > 1) q.push(i), chk[i] = 1;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(auto x : v[u]) {
			merge(u, x);
			if(!chk[x]) q.push(x), chk[x] = 1;
		}
	}

	ll ans = 0;
	for(int i=1;i<=n;i++) if(i == find(i)) ans += 1ll*s[i]*(s[i]-1);
	for(int i=1;i<=n;i++) for(int j : v[i]) if(find(i) != find(j)) ans++;
	cout << ans;
}

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