Submission #870662

#	Time	Username	Problem	Language	Result	Execution time	Memory
870662		fatemetmhr	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	817 ms	87456 KiB

joitter2

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

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define sep      ' '
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const ll  mod   =  1e9   +  7;
const ll  inf   =  2e18;

ll ans;
unordered_set <int> out[maxn5], ex[maxn5], en[maxn5];
vector <int> av[maxn5], mer;
int cmp[maxn5];
queue <int> q;
bool rem[maxn5];

/*
out[a]  = rasayi ke be a (ke moalefas) yal daran;
en[a]   = moalefe hayi ke be a (ke moalefas) yal daran;
ex[a]   = moalafe hayi ke a (ke moalefas) be oona yal dare;
*/


int join(int a, int b){
	if(av[a].size() > av[b].size()) swap(a, b);
	int esh = 0;
	for(auto it = out[a].begin(); it != out[a].end(); it++){
	   	if(cmp[*it] == b) ans -= av[a].size();
	   	else if(out[b].find(*it) == out[b].end()) ans += av[b].size();
	   	if(out[b].find(*it) != out[b].end()) esh++;
	}
	
	/*/ to be removed ;.......................................................................
	for(auto it = out[b].begin(); it != out[b].end(); it++){
		if(cmp[*it] == a) ans -= av[b].size(); // done



		else if(out[a].find(*it) == out[a].end()){
			ans += av[a].size(); 
		}
	}
	// ....................................................................................... */


	ans += ll(av[a].size()) * (out[b].size() - esh); 
	ll sa = av[a].size(), sb = av[b].size();
	ans -= sa * (sa - 1);
	ans -= sb * (sb - 1);
	ans += (sa + sb) * (sa + sb - 1);
	for(auto it = en[a].begin(); it != en[a].end(); it++){
		if(ex[b].find(*it) != ex[b].end()) q.push(*it), mer.pb(*it);
	}
	for(auto it = ex[a].begin(); it != ex[a].end(); it++){
		if(en[b].find(*it) != en[b].end()) q.push(*it), mer.pb(*it);
	}
	for(auto u : mer){
	    en[a].erase(u);
	    ex[a].erase(u);
	    en[b].erase(u);
	    ex[b].erase(u);
	}
	for(auto u : av[a]){
		av[b].pb(u);
		if(out[b].find(u) != out[b].end()) ans -= sb + sa;
		out[b].erase(u);
		cmp[u] = b;
	}
	for(auto it = en[a].begin(); it != en[a].end(); it++){
		ex[*it].erase(a);
		ex[*it].insert(b);
		en[b].insert(*it);
	}
	for(auto it = ex[a].begin(); it != ex[a].end(); it++){
		en[*it].erase(a);
		en[*it].insert(b);
		ex[b].insert(*it);
	}
	for(auto it = out[a].begin(); it != out[a].end(); it++)
		if(cmp[*it] != b) out[b].insert(*it);
	av[a].cl();
	en[a].cl();
	ex[a].cl();
	out[a].cl();
	rem[a] = true;
	mer.cl();
	return b;
}

int main()
{
	//cout << setprecision(15);
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		av[i].pb(i);
		cmp[i] = i;
	}
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		if(cmp[a] != cmp[b]){
			int x = cmp[a], y = cmp[b];
			if(ex[y].find(x) != ex[y].end()){
				int now = x;
				q.push(y);		 
				while(!q.empty()){
					int v= q.front();
					q.pop();
					if(rem[v] or v == now) continue;
					now = join(now, v);
				}
			}
			else if(out[y].find(a) == out[y].end()){
				ans += av[y].size();
				ex[x].insert(y);
				en[y].insert(x);
				out[y].insert(a);
			}
		}
		cout << ans << endll;
	}
	return 0;
}

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