Submission #1058708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058708		0npata	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	1 ms	4956 KiB

joitter2

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

#define int long long
#define vec vector

struct DSU {
	vec<int> par;
	vec<int> sz;

	DSU(int n) {
		par = vec<int>(n);
		iota(par.begin(), par.end(), 0);
		sz = vec<int>(n, 1);
	}

	int root(int x) {
		if(par[x] == x) return x;
		par[x] = root(par[x]);
		return par[x];
	}

	bool join(int x, int y) {
		x = root(x);
		y = root(y);
		if(x==y) return false;
		if(sz[x] < sz[y]) swap(x, y);
		par[y] = x;
		sz[x] += sz[y];
		sz[y] = 0;
		return true;
	}
};

const int MXN = 100'005;

set<int> g[MXN];

int32_t main() {
	int N, M;
	cin >> N >> M;

	DSU dsu(N);

	while(M--) {
		int u, v;
		cin >> u >> v;
		u--;v--;
		g[u].insert(v);
		if(g[v].count(u)) {
			dsu.join(u, v);
		}

		if(false){
		cerr << "DSU INFO" << '\n';
		for(int i = 0; i<N; i++) cerr << dsu.root(i) << ' ';
		cerr << '\n';
		for(int i = 0; i<N; i++) {
			cerr << dsu.sz[i] << ' ';
		}
		cerr << '\n';
		}

		int ans = 0;
		for(int u = 0; u<N; u++) {
			set<int> comp_ignore{dsu.root(u)};
			for(int v : g[u]) {
				if(!comp_ignore.count(dsu.root(v))) {
					ans += dsu.sz[dsu.root(v)];
					comp_ignore.insert(dsu.root(v));
				}
			}
			//cerr << ans << ' ';
			ans += dsu.sz[u]*(dsu.sz[u]-1);
		}

		cout << ans << '\n';
	}

}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83