oj.uz

Submission #1058708

# Submission time Handle Problem Language Result Execution time Memory
1058708 2024-08-14T12:40:43 Z 0npata Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 1 ms 4956 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -