Submission #388090

#	Time	Username	Problem	Language	Result	Execution time	Memory
388090		pure_mem	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	11 ms	14432 KiB

joitter2

#include <bits/stdc++.h> 
 
#define X first
#define Y second
#define MP make_pair
#define ll long long
 
using namespace std;
 
const int MAXN = 1e5 + 12;
            
int n, m, dsu[MAXN];
set< int > children[MAXN], graph[MAXN], rgraph[MAXN];
queue< pair<int, int> > to_merge;
ll answer, sz[MAXN];

void merge(int a, int b){
	graph[a].insert(b);
	rgraph[b].insert(a);
	if(graph[b].count(a))
		to_merge.push(MP(a, b));
}

int get_pr(int v){
	if(dsu[v] == v)
		return v;
	return dsu[v] = get_pr(dsu[v]);
}

int dsu_size(int a){
	return children[a].size() + graph[a].size() + rgraph[a].size();
}

void dsu_merge(int a, int b){
	if(a == b)
		return;
	if(dsu_size(a) < dsu_size(b))
		swap(a, b);
	answer += sz[b] * children[a].size() + sz[a] * children[b].size();
	dsu[b] = a, sz[a] += sz[b];
	for(int i: children[b]){
		if(children[a].count(i)) 
			answer -= sz[a];
		else
			children[a].insert(i);
	}
	graph[a].erase(b), rgraph[a].erase(b);
	graph[b].erase(a), rgraph[b].erase(a);
	for(int i: graph[b]){
		rgraph[i].erase(b);
		merge(a, i);
	}
	for(int i: rgraph[b]){
		graph[i].erase(b);
		merge(i, a);
	}
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		sz[i] = 1, dsu[i] = i, children[i].insert(i);
	for(int a, b;m--;){
		cin >> a >> b;
		b = get_pr(b);
		if(get_pr(a) != b && !children[b].count(a)){
			children[b].insert(a);
			answer += sz[b];
			a = get_pr(a);
			merge(a, b);
			while(!to_merge.empty()){
				tie(a, b) = to_merge.front();
				to_merge.pop();
				dsu_merge(a, b);
			}	
		}
		cout << answer << "\n";	
	}
}               

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