제출 #1153686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153686		beaboss	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	0 / 100	5 ms	10048 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<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

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

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

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

const int N = 1e5 + 10;

set<int> in[N], out[N];
vi p(N,- 1);

long long res = 0;

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

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

void unite(int a, int 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();


	if (-p[a] > -p[b]) {
		// swap(in[a], in[b]);
		// swap(out[a], out[b]);
		swap(a, b);	
	}

	// 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;

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

	set<int> future_merge;

	for (auto x: in[a]) {
		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].erase(a);
		in[x].insert(b);
	}

	// for (auto val: in[b]) cout << val << endl;

	// cout << in[b].size() << out[b].size() << -p[b] << ' ' << res << 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);

	int n, m;
	cin >> n >> m;

	FOR(i, 0, m) {
		int x, y;
		cin >> x >> y;
		x=get(x);
		y=get(y);
		// cout << x << y << endl;
		if (x != y) {
			if (in[y].count(x) == 0) res+=-p[y];
			in[y].insert(x);
			out[x].insert(y);
			
			if (out[y].find(x) != out[y].end()) unite(x, y);
		}
		cout << res << endl;
	}
}

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