Submission #1059128

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

joitter2

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

#define int long long
#define vec vector


struct DSU {
	vec<int> par;
	vec<int> sz;
	vec<map<int, set<int>>> outc;
	vec<map<int, set<int>>> inc;
	vec<pair<int, int>> to_merge;
	vec<int> total_inc_size;
	int ans = 0;

	DSU(int n) {
		par = vec<int>(n);
		iota(par.begin(), par.end(), 0);
		sz = vec<int>(n, 1);
		inc = vec<map<int, set<int>>>(n);
		outc = vec<map<int, set<int>>>(n);
		total_inc_size = vec<int>(n);
		to_merge = {};
	}

	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;
		//cerr << "MERGING: " << x << ' ' << y << '\n';

		if(sz[x] < sz[y]) swap(x, y);

		ans -= total_inc_size[x] * sz[x];
		ans -= total_inc_size[y] * sz[y];
		total_inc_size[x] -= inc[x][y].size();
		total_inc_size[y] = 0;
		inc[x].erase(y);
		inc[y].erase(x);
		outc[x].erase(y);
		outc[y].erase(x);
		ans -= sz[x]*(sz[x]-1);
		ans -= sz[y]*(sz[y]-1);

		for(auto [c, _] : outc[y]) {
			for(int vertex : inc[c][y]) {
				inc[c][x].insert(vertex);
			}
			inc[c].erase(y);
		}
		for(auto [c, _] : inc[y]) {
			for(int vertex : outc[c][y]) {
				outc[c][x].insert(vertex);
			}
			outc[c].erase(y);
		}

		for(auto [c, vertices] : inc[y]) {
			for(int v : vertices) {
				total_inc_size[x] -= inc[x][c].size();
				inc[x][c].insert(v);
				assert(root(v) == c);
				if(outc[x][c].size() > 0) {
					to_merge.push_back({x, v});
				}
				total_inc_size[x] += inc[x][c].size();
			}
		}
		for(auto [c, vertices] : outc[y]) {
			for(int v : vertices) {
				outc[x][c].insert(v);
				//assert(root(v) == c);
				if(inc[x][c].size() > 0) {
					to_merge.push_back({x, v});
				}
			}
		}

		inc[y] = {};
		outc[y] = {};

		par[y] = x;
		sz[x] += sz[y];
		sz[y] = 0;

		ans += total_inc_size[x] * sz[x];
		ans += sz[x]*(sz[x]-1);

		return true;
	}

	void merge_all() {
		while(to_merge.size() > 0) {
			auto [x, y] = to_merge.back();
			to_merge.pop_back();
			join(x, y);
		}
	}

	void make_edge(int u, int v) {
		for(int i = 0; i<par.size(); i++) {
			for(auto [c, vs] : outc[i]) {
				//for(int v : vs) assert(root(v) == c);
			}
		}
		for(int i = 0; i<par.size(); i++) {
			for(auto [c, vs] : inc[i]) {
				for(int v : vs) assert(root(v) == c);
			}
		}

		if(root(u) == root(v)) return;
		ans -= total_inc_size[root(v)] * sz[root(v)];

		outc[root(u)][root(v)].insert(u);

		total_inc_size[root(v)] -= inc[root(v)][root(u)].size();
		inc[root(v)][root(u)].insert(u);
		total_inc_size[root(v)] += inc[root(v)][root(u)].size();

		ans += total_inc_size[root(v)] * sz[root(v)];
		if(outc[root(u)][root(v)].size() > 0 && inc[root(u)][root(v)].size() > 0) {
			to_merge.push_back({u, v});
			merge_all();
		}
	}
};

const int MXN = 100'005;


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

	DSU dsu(N);

	while(M--) {
		int u, v;
		cin >> u >> v;
		u--;v--;

		dsu.make_edge(u, v);

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

}

Compilation message (stderr)

joitter2.cpp: In member function 'void DSU::make_edge(long long int, long long int)':
joitter2.cpp:108:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for(int i = 0; i<par.size(); i++) {
      |                  ~^~~~~~~~~~~
joitter2.cpp:113:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i = 0; i<par.size(); i++) {
      |                  ~^~~~~~~~~~~

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