Submission #513904

#	Time	Username	Problem	Language	Result	Execution time	Memory
513904		Eyed	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	6 ms	14412 KiB

joitter2

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll MOD = 1e9 + 7;

//Making Friends on Joitter is Fun: JOI 2020/2
//Problem: https://oj.uz/problem/view/JOI20_joitter2

int n, m;
//set<int> conTo[100005]; //ConTo[a] contains things that connect to group a
set<int> conU[100005]; //conU[a] contains a cup conTo[a]
set<int> tGraph[100005]; // graph of arrows from pA to pB
set<int> bGraph[100005];
int cSize[100005];
int up[100005];
int sumT[100005]; //sumT[a] = sum of cSize[x] for x in conTo[a] 
int curAns;
queue<pii> merg;

void goIn(int a, int b) {
	tGraph[a].insert(b);
	bGraph[b].insert(a);
	if (tGraph[b].find(a) != tGraph[b].end()) merg.push({ a,b });
}

int par(int b) {
	return (b == up[b] ? b : (up[b] = par(up[b])));
}

void con(int a, int b) {//connects a to b
	if (a == b) return;
	curAns += conU[a].size() * cSize[b];
	curAns += conU[b].size() * cSize[a];
	if (conU[a].size() < conU[b].size()) swap(a, b);
	for (auto itr = conU[b].begin(); itr != conU[b].end(); ++itr) {
		if (conU[a].find(*itr) != conU[a].end()) curAns -= (cSize[a] + cSize[b]);
	}
	for (auto itr = conU[b].begin(); itr != conU[b].end(); ++itr) {
		conU[a].insert(*itr);
	}
	up[b] = a;
	cSize[a] += cSize[b];

	tGraph[a].erase(b);
	tGraph[b].erase(a);
	bGraph[a].erase(b);
	bGraph[b].erase(a);
	for (int i : tGraph[b]) {
		bGraph[i].erase(b);
		goIn(a, i);
	}
	for (int i : bGraph[b]) {
		tGraph[i].erase(b);
		goIn(i, a);
	}

}
void init() {
	for (int i = 1; i <= n; ++i) {
		cSize[i] = 1;
		up[i] = i;
		conU[i].insert(i);
	}
	curAns = 0;
}

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

	cin >> n >> m;
	init();
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		b = par(b);
		if (par(a) != b && conU[b].find(a) == conU[b].end()) {
			conU[b].insert(a);
			curAns += cSize[b];
			a = par(a);
			goIn(a, b);
			while (!merg.empty()) {
				pii p = merg.front();
				merg.pop();
				con(par(a), par(b));
			}
		}
		cout << curAns << endl;
	}
	return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:92:9: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   92 |     pii p = merg.front();
      |         ^

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