Submission #927750

#	Time	Username	Problem	Language	Result	Execution time	Memory
927750		vjudge1	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	856 ms	69452 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 100005
#define fi first
#define se second

typedef pair<int, int> ii;

set<int> adj[N], radj[N], st[N];
int pr[N], siz[N], n, m, res = 0;
queue<ii> q;

int find(int u){
	if (u == pr[u]) return u;
	return pr[u] = find(pr[u]);
}

void bl(int a, int b){
	adj[a].insert(b);
	radj[b].insert(a);
	if (adj[b].count(a)){
		q.push({a, b});
	}
}

int getsiz(int a){
	return st[a].size() + adj[a].size() + radj[a].size();
}

void unin(int a, int b){
	if (a == b) return;
	res += siz[a] * st[b].size() + siz[b] * st[a].size();
	if (getsiz(a) < getsiz(b)) swap(a, b);
	pr[b] = a;
	siz[a] += siz[b];
	for (auto x : st[b]){
		if (st[a].count(x)) res -= siz[a];
		else st[a].insert(x);
	}
	adj[a].erase(b);
	radj[a].erase(b);
	adj[b].erase(a);
	radj[b].erase(a);
	for (auto x : adj[b]){
		radj[x].erase(b);
		bl(a, x);
	}
	for (auto x : radj[b]){
		adj[x].erase(b);
		bl(x, a);
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
    	siz[i] = 1;
    	pr[i] = i;
    	st[i].insert(i);
    }

    while (m--){
    	int a, b;
    	cin >> a >> b;
    	b = find(b);
    	if (find(a) != b && !st[b].count(a)){
    		st[b].insert(a);
    		res += siz[b];
    	 	a = find(a);
    	 	bl(a, b);
    	 	while (!q.empty()){
    	 		a = q.front().fi;
    	 		b = q.front().se;
    	 		q.pop();
    	 		unin(find(a), find(b));
    	 	}
    	}	
    	cout << res << "\n";
    }

    return 0;
}     

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