Submission #212294

#	Time	Username	Problem	Language	Result	Execution time	Memory
212294		ksun48	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1197 ms	64888 KiB

joitter2

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

using ll = long long;

int n, m;

ll cnt = 0;

vector<int> par;
vector<vector<int> > group;
vector<set<int> > group_edges;

vector<set<int> > group_followers;
vector<set<int> > person_following;

void add_edge(int a, int gb);

void add_group_edge (int ga, int gb) {
	ga = par[ga];
	gb = par[gb];
	if(ga == gb) return;
	if(group_edges[ga].count(gb)) return;
	group_edges[ga].insert(gb);
	if(group_edges[gb].count(ga)){
		if(group[ga].size() < group[gb].size()) swap(ga, gb);

		vector<pair<int,int> > add_edges;

		while(!group_followers[gb].empty()){
			int a = *group_followers[gb].begin();
			cnt -= (int)group[gb].size();
			group_followers[gb].erase(a);
			person_following[a].erase(gb);
			add_edges.push_back({a, gb});
		}
		for(int b : group[gb]){
			while(!person_following[b].empty()){
				int gc = *person_following[b].begin();
				cnt -= (int)group[gc].size();
				person_following[b].erase(gc);
				group_followers[gc].erase(b);
				add_edges.push_back({b, gc});
			}
		}

		cnt -= 1ll * ((int)group[ga].size()) * ((int)group[ga].size() - 1);
		cnt -= 1ll * ((int)group[gb].size()) * ((int)group[gb].size() - 1);
		for(int x : group[gb]){
			par[x] = ga;
			group[ga].push_back(x);
		}
		cnt += 1ll * ((int)group[ga].size()) * ((int)group[ga].size() - 1);
		cnt += 1ll * ((int)group_followers[ga].size()) * ((int)group[gb].size());
		for(pair<int,int> x : add_edges){
			add_edge(x.first, x.second);
		}
	}
}

void add_edge(int a, int b){
	int ga = par[a];
	int gb = par[b];
	if(ga == gb) return;
	if(person_following[a].count(gb)) return;
	cnt += (int)group[gb].size();
	person_following[a].insert(gb);
	group_followers[gb].insert(a);
	add_group_edge(ga, gb);
}

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;
	par.resize(n), group.resize(n), group_edges.resize(n);
	group_followers.resize(n), person_following.resize(n);

	for(int i = 0; i < n; i++){
		par[i] = i;
		group[i].push_back(i);
	}

	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		add_edge(a, b);
		cout << cnt << '\n';
	}
}

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