Submission #1153884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153884		beaboss	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	1179 ms	117568 KiB

joitter2

// Source: https://oj.uz/problem/view/JOI20_joitter2
//

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }

const ll N = 1e5 + 10;

set<ll> in[N], group[N], comp[N], ocomp[N]; // out is the set of outgoing people and ingoing followers
vi p(N,- 1);

long long res = 0;

ll p2(ll x) {
	return x * (x-1);
}

ll get(ll x) {
	return p[x] < 0 ? x : p[x] = get(p[x]);
}

void unite(ll a, ll b) {
	a = get(a);b=get(b);
	if (a==b) return;
	// cout <<  a << in[a].size() << endl;
	res -= p2(-p[a]) + p2(-p[b]) + (-p[a]) * (in[a].size()) + (-p[b]) * in[b].size();
	// cout << res << endl;

	if (-p[a] > -p[b]) {
		// swap(in[a], in[b]);
		// swap(out[a], out[b]);
		swap(a, b);	
	}
	// cout << a << b << endl;
	// cout << res << endl;
	// if (in[a].size() > in[b].size()) swap(in[a], in[b]);
	// if (out[a].size() > out[b].size()) swap(out[a], out[b]);

	p[b] += p[a];
	p[a]=b;

	comp[b].erase(a);

	set<ll> future_merge;


	for (auto x: ocomp[a]) {
		if (x != b) {
			if (ocomp[x].count(b)) future_merge.insert(x);
			comp[x].erase(a);
			comp[x].insert(b);
			ocomp[b].insert(x);
		}
	}

	for (auto x: comp[a]) {
		if (x != b) {
			if (comp[x].count(b)) future_merge.insert(x);
			ocomp[x].erase(a);
			ocomp[x].insert(b);
			comp[b].insert(x);
		}
	}

	for (auto x: group[a]) {
		if (in[b].count(x)) in[b].erase(x);
		group[b].insert(x);
	}



	for (auto x: in[a]) {
		ll xx = get(x);
		// if (comp[xx].find(b) != comp[xx].end()) future_merge.insert(xx);
		if (xx != b) {
			in[b].insert(x);
			comp[b].insert(xx);
		}
	}

	// out[b].erase(a);
	// out[a].erase(b);



	// set<ll> future_merge;

	// for (auto x: in[a]) {
	// 	if (get(x) == b) continue;

	// 	in[b].insert(x);
	// 	if (out[b].find(x) != out[b].end())
	// 		future_merge.insert(x);

	// 	out[x].erase(a);
	// 	out[x].insert(b);
	// }

	// for (auto x: out[a]) {
	// 	out[b].insert(x);
	// 	if (in[b].find(x) != in[b].end())
	// 		future_merge.insert(x);

	// 	in[x].insert(b);
	// }


	// cout << -p[b] << endl;

	res += p2(-p[b]) + (-p[b]) * in[b].size();

	for (auto x: future_merge) unite(x, b);
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll n, m;
	cin >> n >> m;

	FOR(i,1,n+1) group[i].insert(i);

	FOR(i, 0, m) {
		ll xx, yy;
		cin >> xx >> yy;

		ll x=get(xx);
		ll y=get(yy);
		// cout << x << y << endl;
		if (x != y) {
			if (in[y].count(xx) == 0) res+=-p[y];
			in[y].insert(xx);
			comp[y].insert(x);
			ocomp[x].insert(y);
			// cout << y << xx << ' ' << x << endl;
			if (comp[x].find(y) != comp[x].end()) unite(x, y);
		}
		cout << res << endl;
	}
}

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