Submission #416567

#	Time	Username	Problem	Language	Result	Execution time	Memory
416567		amirmohammad_nezami	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1679 ms	88748 KiB

joitter2

//                                                          In the name of God 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define lc 2 * v
#define rc 2 * v + 1
#define mid (s + e) / 2
#define _sz(e) (int)e.size()
#define _all(e) e.begin() , e.end()
#define _lcm(a , b) (1ll * a * b) / __gcd(a , b)
#define ll long long
#define int long long
#define ld long double
#define pii pair <int , int>
#define pcc pair <char , char>
#define pll pair <long long , long long>
#define piii pair <int , pair <int , int>>
#define FAST ios::sync_with_stdio(0);cin.tie(0)
#pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avmini,avmini2")

const int maxn = 2e5 + 10 , N = 2e6 + 10 , SQ = 320 , base = 800287 , mod = 1e9 + 7 , INF = 1e18 + 10 , lg = 22;
const ld eps = 1e-4;

int n , m , ans , sz[maxn] , par[maxn];
set <int> edges[maxn] , revedges[maxn] , inn[maxn];
queue <pii> q;

int root(int v) {
	return (par[v] == v ? v : par[v] = root(par[v]));
}

inline void add_edge(int v , int u) {
	edges[v].insert(u) , revedges[u].insert(v);
	if(edges[u].find(v) != edges[u].end()) {
		q.push({v , u});
	}
}

void merge(int v , int u) {
	if(v == u) {return ;}
	int sz1 = _sz(edges[v]) + _sz(revedges[v]) + _sz(inn[v]);
	int sz2 = _sz(edges[u]) + _sz(revedges[u]) + _sz(inn[u]);
	if(sz1 < sz2) {swap(v , u);}

	ans += (sz[v] * 1ll * _sz(inn[u])) + (sz[u] * 1ll *  _sz(inn[v]));
	sz[v] += sz[u] , par[u] = v;

	for (auto x : inn[u]) {
		if(inn[v].find(x) != inn[v].end()) {
			ans -= sz[v];
		}
		else {
			inn[v].insert(x);
		}
	}

	edges[v].erase(u) , revedges[v].erase(u);
	edges[u].erase(v) , revedges[u].erase(v);

	for (auto x : edges[u]) {
		revedges[x].erase(u);
		add_edge(v , x);
	}
	for (auto x : revedges[u]) {
		edges[x].erase(u);
		add_edge(x , v);
	}
	edges[u].clear() , revedges[u].clear() , inn[u].clear();
}

int32_t main() {	
	FAST;
	cin >> n >> m;
	iota(par , par + maxn , 0);
	fill(sz , sz + maxn , 1);
	for (int i = 0; i < maxn; ++i) {
		inn[i].insert(i);
	}

	for (int i = 0; i < m; ++i) {
		int x , y; cin >> x >> y;
		x-- , y = root(y - 1);
		if(root(x) == y || inn[y].find(x) != inn[y].end()) {
			cout << ans << '\n';
			continue;
		}

		inn[y].insert(x);
		ans += sz[y];
		add_edge(root(x) , y);

		while(_sz(q)) {
			pii p = q.front();
			merge(root(p.F) , root(p.S));
			q.pop();
		}

		cout << ans << '\n';
	}	
} 

//  Mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.

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