Submission #472364

#	Time	Username	Problem	Language	Result	Execution time	Memory
472364		sidon	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1769 ms	86800 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define sz(Z) ll(size(Z))
 
const int MAX_N = 100'001;
 
int N, M;
 
int P[MAX_N];
ll edge_count;
 
set<int> g[MAX_N], h[MAX_N], c[MAX_N];
unordered_map<int, int> degree[MAX_N];
 
queue<array<int, 2>> Q;
 
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
 
	cin >> N >> M;
 
	for(int u = 1; u <= N; ++u){
		P[u] = u;
		c[u] = {u};
	}
 
	while(M--){
		int A, B;
		cin >> A >> B;
 
		int u = P[A], v = P[B];
 
		if(u == v || h[v].find(A) != end(h[v])){
			cout << edge_count << '\n';
			continue;
		}
 
		if(g[v].find(u) != end(g[v]))
			Q.push({u, v});
 
		edge_count += sz(c[v]);
 
		h[v].insert(A);
		g[u].insert(v);
		++degree[u][v];
 
		while(!empty(Q)) {
			u = P[Q.front()[0]], v = P[Q.front()[1]];
			Q.pop();
			if(u == v) continue;
 
			if(sz(g[u]) + sz(h[u]) + sz(c[u]) < sz(g[v]) + sz(h[v]) + sz(c[v]))
				swap(u, v);
 
			edge_count += (sz(c[u]) - degree[u][v]) * sz(c[v]);
			edge_count += (sz(c[v]) - degree[v][u]) * sz(c[u]);
 
			for(int w : g[v]) {
				if(g[P[w]].find(u) != end(g[P[w]])) Q.push({u, w});
				degree[u][P[w]] += degree[v][P[w]];
				degree[v][P[w]] = 0;
			}
 
			for(auto i = begin(h[v]); i != end(h[v]); ) {
				if(g[u].find(P[*i]) != end(g[u])) Q.push({u, *i});
 
				if(P[*i] == u) {
					i = h[v].erase(i);
				} else {
					if(h[u].find(*i) != end(h[u]))
						edge_count -= (sz(c[u]) + sz(c[v]));
					else {
						g[P[*i]].insert(u);
						++degree[P[*i]][u];
					}
					++i;
				}
			}
 
			for(int w : c[v]) {
				auto f = h[u].find(w);
				if(f != end(h[u])) h[u].erase(f);
				P[w] = u;
			}
 
			edge_count += sz(h[u]) * sz(c[v]);
			edge_count += sz(h[v]) * sz(c[u]);
 
			g[u].merge(g[v]);
			h[u].merge(h[v]);
			c[u].merge(c[v]);
		}
 
		cout << edge_count << '\n';
	}
}

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