Submission #1179522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179522		KK_1729	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	881 ms	66072 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}
int ans = 0;
queue<pair<int, int>> to_merge;
struct UFDS{
	vector<int> link, siz;
	vector<set<int>> child, graph, rgraph;
	UFDS (int n){


		link.resize(n+1);
		for (int i = 0; i <= n; i++) link[i] = i;

		siz.resize(n+1, 1);
		child.resize(n+1);
		graph.resize(n+1);
		for (int i = 0; i <= n; ++i) child[i].insert(i);
		rgraph.resize(n+1);
	}

	int dsu_size(int x){
		return (int)(child[x].size() + graph[x].size() + rgraph[x].size());
	}
	int find(int x){
		if (x == link[x]) return x;
		return link[x] = find(link[x]);
	}


	void insert_conn(int x, int y){
		graph[x].insert(y);
		rgraph[y].insert(x);
		if (graph[y].count(x)) to_merge.push({x, y});
	}
	void unite(int x, int y){
		x = find(x);
		y = find(y);

		if (x == y) return;

		if (dsu_size(x) < dsu_size(y)) swap(x, y);


		ans += child[x].size()*siz[y] + child[y].size()*siz[x];
		link[y] = x;
		siz[x] += siz[y];

		for (auto i: child[y]){
			if (child[x].count(i) == 0) child[x].insert(i);
			else ans -= siz[x];
		}

		graph[x].erase(y);rgraph[y].erase(x);
		graph[y].erase(x);rgraph[x].erase(y);
		for (auto i: graph[y]){
			rgraph[i].erase(y);
			insert_conn(x, i);
		}
		for (auto i: rgraph[y]){
			graph[i].erase(y);
			insert_conn(i, x);
		}

	}
};
void solve(){

	int n, m; cin >> n >> m;
	UFDS ds(n+1);
	FOR(k,0,m){
		int x, y; cin >> x >> y;
		y = ds.find(y);
		if (ds.find(x) != y && !ds.child[y].count(x)){
			ds.child[y].insert(x);
			ans += ds.siz[y];

			x = ds.find(x);
			ds.insert_conn(x, y);

			while (to_merge.size()){
				tie(x, y) = to_merge.front();
				to_merge.pop();
				ds.unite(x, y);
			}


		}

		cout << ans << endl;
	}
}


int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int t = 1; // cin >> t;
	while (t--) solve();
}

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