제출 #834723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834723		ToniB	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	7 ms	15188 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 2;

int n, m, uf[MAXN], sz[MAXN], cnt_inside[MAXN];
ll ans;
set<int> in[MAXN], out[MAXN];
unordered_map<int, bool> edge[MAXN];

int f(int x){
	while(uf[x] != -1) x = uf[x];
	return x;
}

void merge_set(set<int>& a, set<int>& b){
	if(a.size() > b.size()) swap(a, b);
	for(int x : a) b.insert(x);
}

void join(int u, int v){
	ans += 2LL * sz[u] * sz[v];
	ans -= (ll)sz[u] * (in[u].size() - cnt_inside[u]) + (ll)sz[v] * (in[v].size() - cnt_inside[v]);
	if(out[u].size() + in[u].size() > out[v].size() + in[v].size()) swap(u, v);
	int nxt = -1;
	
	for(int x : out[u]){
		if(edge[x][v] && f(x) != v) nxt = x;
	}
	for(int x : in[u]){
		edge[x][v] = 1;
		if(edge[v][x] && f(x) != v) nxt = x;
	}
	for(int x : out[u]){
		if(f(x) == v) ++cnt_inside[v];
	}
	for(int x : in[u]){
		if(f(x) == v) ++cnt_inside[v];
	}

	merge_set(out[u], out[v]);
	merge_set(in[u], in[v]);

	uf[u] = v;
	sz[v] += sz[u];
	cnt_inside[v] += cnt_inside[u];
	
	ans += (ll)sz[v] * (in[v].size() - cnt_inside[v]);
	
	if(nxt != -1) join(f(nxt), v);
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < n; ++i) uf[i] = -1, sz[i] = 1;

	for(int i = 0; i < m; ++i){
		int u, v; cin >> u >> v, --u, --v;
		int fu = f(u), fv = f(v);
		if(fu == fv){
			++cnt_inside[fu];
			in[fu].insert(fu);
			out[fu].insert(fu);
			continue;
		}
		bool exist = 0;
		for(int x : out[fv]){
			if(f(x) == fu) exist = 1;
		}
		if(exist){
			join(fu, fv);
		} else {
			if(!edge[u][fv]){
				edge[u][fv] = 1;
				ans += sz[fv];
			}
			in[fv].insert(u);
			out[fu].insert(v);
		}

		cout << ans << "\n";
	}
	return 0;
}

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