제출 #472164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472164		sidon	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	12 ms	19788 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(h[u].find(P[w]) != end(h[u])) Q.push({u, w});
				++degree[u][P[w]];
			}

			for(auto i = begin(h[v]); i != end(h[v]); ) {
				if(g[u].find(P[*i]) != end(g[u])) Q.push({u, *i});

				if(c[u].find(*i) != end(c[u])) {
					i = h[v].erase(i);
				} 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: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83