Submission #1300190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300190		Jawad_Akbar_JJ	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	4 ms	7480 KiB

joitter2

#include <iostream>
#include <queue>
#include <set>

using namespace std;
const int N = 1<<17;
set<pair<int,int>> in[N], out;
int Ans, Par[N], Sz[N];
queue<pair<int, int>> Q;

int root(int u){
	return (Par[u] == u ? u : Par[u] = root(Par[u]));
}

void inUpd(int t, int v1, pair<int, int> pr){
	Ans -= in[v1].size() * Sz[v1];
	if (t == 1)
		in[v1].insert(pr);
	else
		in[v1].erase(pr);
	Ans += in[v1].size() * Sz[v1];
}

void inErase(int v1, int v2){
	auto u = in[v1].upper_bound({v2, -1});
	while (u != in[v1].end() and (*u).first == v2){
		u = next(u);
		inUpd(0, v1, *prev(u));
	}
}

void connect(int A, int B){
	A = root(A), B = root(B);
	if (A == B)
		return;
	
	if (in[A].size() < in[B].size())
		swap(A, B);
	Ans -= Sz[A] * (Sz[A] - 1) + Sz[B] * (Sz[B] - 1);
	Sz[A] += Sz[B];
	Ans += in[A].size() * Sz[B];
	Ans += Sz[A] * (Sz[A] - 1);
	Par[B] = A;

	for (auto [i, j] : in[B]){
		if (out.find({A, i}) != out.end())
			Q.push({A, i});
		Ans -= Sz[B];
		inUpd(1, A, {i, j});
		out.erase({i, B});
		out.insert({i, A});
	}
	set<pair<int,int>> ().swap(in[B]);
}

int main(){
	for (int i=1;i<N;i++)
		Sz[i] = 1, Par[i] = i;
	int n, m, a, b, A, B;
	cin>>n>>m;

	while (m--){
		cin>>a>>b;
		A = root(a), B = root(b);
		
		auto u = in[A].upper_bound({B, -1});
		out.insert({A, B});
		inUpd(1, B, {A, a});

		if (u != in[A].end() and (*u).first == B)
			Q.push({A, B});


		while (Q.size() > 0){
			A = Q.front().first, B = Q.front().second, Q.pop();
			inErase(A, B), inErase(B, A);
			connect(A, B); 
		}

		cout<<Ans<<'\n';
	}
}

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