제출 #856874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856874		serifefedartar	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	890 ms	69084 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18; 
const ll INF = 1e15;
const ll MAXN = 1e5 + 5;
 
vector<set<int>> graph, rev;
queue<pair<int,int>> q;
set<int> in[MAXN];
int par[MAXN];
ll sz[MAXN];
ll ans = 0;
int find(int node) {
	if (par[node] == node)
		return node;
	return par[node] = find(par[node]);
}
 
void conn(int from, int to) {
	graph[from].insert(to);
	rev[to].insert(from);
	if (graph[to].count(from))
		q.push({from, to});	
}
 
void merge(int x, int y) {
	if (x == y)
		return ;
	if (graph[x].size() + rev[x].size() + in[x].size() < graph[y].size() + rev[y].size() + in[y].size())
 		swap(x, y);
 
	ans += in[y].size() * sz[x] + in[x].size() * sz[y]; 
	sz[x] += sz[y];
	par[y] = x;
 		
	for (auto u : in[y]) {
		if (in[x].count(u) == 0)
			in[x].insert(u);
		else
			ans -= sz[x];
	}
 
	graph[x].erase(y);
	graph[y].erase(x);
	rev[x].erase(y); 
	rev[y].erase(x);
	for (auto u : graph[y]) {
		rev[u].erase(y);
		conn(x, u); 
	}
	for (auto u : rev[y]) {
		graph[u].erase(y);
		conn(u, x);
	}
}
 
int main() {
	fast
	int N, M, a, b;
	cin >> N >> M;
 
	for (int i = 1; i <= N; i++) {
		par[i] = i, sz[i] = 1;
		in[i].insert(i);
	}
	graph = vector<set<int>>(N+1, set<int>());
	rev = vector<set<int>>(N+1, set<int>());
 
	for (int i = 1; i <= M; i++) {
		cin >> a >> b;
		int par_a = find(a);
		int par_b = find(b);
 
		if (par_b == par_a) {
			cout << ans << "\n";
			continue;
		}
		if (in[par_b].count(a) == 0) {
			in[par_b].insert(a);
			ans += sz[par_b];
 
			conn(par_a, par_b);
			while (!q.empty()) {
				int from = q.front().f;
				int to = q.front().s;
				q.pop();
				merge(find(from), find(to));
			}
		}
		cout << ans << "\n";
	}
}

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