Submission #219493

#	Time	Username	Problem	Language	Result	Execution time	Memory
219493		atoiz	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1400 ms	81528 KiB

joitter2

/*input
5 5
1 2
3 4
4 1
5 3
1 4
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <ctime>

using namespace std;

const int MAXN = 100007;
int N, M;
int root[MAXN];
int64_t E = 0, cnt[MAXN], deg_in[MAXN], deg_out[MAXN];
unordered_map<int, unordered_set<int>> edges[MAXN];
unordered_set<int> back_edges[MAXN];

stack<pair<int, int>> join_stack;

void init()
{
	for (int u = 1; u <= N; ++u) cnt[u] = 1, root[u] = u;
}

int get_root(int u) { return (root[u] == u ? u : root[u] = get_root(root[u])); }

void delete_edge(int u, int v)
{
	auto it = edges[u].find(v);
	assert(it != edges[u].end());

	int64_t cur = it->second.size() * cnt[v];
	deg_out[u] -= it->second.size(), deg_in[v] -= it->second.size(), E -= cur;
	edges[u].erase(it);
	back_edges[v].erase(u);
}

void add_edge(int u, int v, unordered_set<int> sources)
{
	back_edges[v].insert(u);
	for (int x : sources) {
		if (edges[u][v].find(x) == edges[u][v].end()) {
			++deg_out[u], ++deg_in[v], E += cnt[v];
			edges[u][v].insert(x);
		}
	}	
}

void join(int u, int v)
{
	u = get_root(u), v = get_root(v);
	if (u == v) return;

	if (deg_in[u] + deg_out[u] < deg_in[v] + deg_out[v]) swap(u, v);

	// between u and v
	if (edges[u].find(v) != edges[u].end()) delete_edge(u, v);
	if (edges[v].find(u) != edges[v].end()) delete_edge(v, u);
	E += cnt[u] * cnt[v] * 2;
	// cout << "X " << E << endl;

	auto edges_v = edges[v];
	for (auto batch : edges_v) {
		int w = batch.first;
		delete_edge(v, w);
		if (back_edges[u].find(w) != back_edges[u].end()) join_stack.emplace(u, w);
		else {
			add_edge(u, w, batch.second);
		}
	}

	auto back_edges_v = back_edges[v];
	for (int w : back_edges_v) {
		auto sources = edges[w][v];
		delete_edge(w, v);
		if (back_edges[w].find(u) != back_edges[w].end()) join_stack.emplace(u, w);
		else {
			add_edge(w, u, sources);
		}
	}

	E += cnt[v] * deg_in[u];
	cnt[u] += cnt[v];
	root[v] = u;
}

void query(int u, int v)
{
	unordered_set<int> sources = {u};
	int root_u = get_root(u), root_v = get_root(v);
	if (root_u == root_v) return;
	add_edge(root_u, root_v, sources);
	// cout << "Y " << E << endl;

	if (back_edges[root_u].find(root_v) != back_edges[root_u].end()) {
		join_stack.emplace(root_u, root_v);
	}

	while (!join_stack.empty()) {
		auto p = join_stack.top();
		join_stack.pop();
		join(p.first, p.second);
		// cout << "join " << p.first << ' ' << p.second << ": " << E << endl;
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	init();
	while (M--) {
		int u, v;
		cin >> u >> v;
		query(u, v);
		cout << E << '\n';
	}
	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}

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