Submission #852262

#	Time	Username	Problem	Language	Result	Execution time	Memory
852262		mat_jur	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	1 ms	452 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

class UF {
public:
	int N;
	vector<int> e;
	vector<set<int>> to;
	vector<set<int>> c;
	queue<pair<int, int>> to_merge;
	ll res;
	UF(int n) {
		N = n;
		e.resize(N, -1);
		to.resize(N);
		c.resize(N);
		REP(i, N) c[i].insert(i);
		res = 0;
	}
	int get(int a) {return e[a]<0?a:e[a] = get(e[a]);}
	int sz(int a) {return -e[get(a)];}
	int all_sz(int a) {return ssize(to[a])+ssize(c[a]);}
	void addEdge(int a, int b) {
		assert(a == get(a) && b == get(b));
		to[a].insert(b);
		if (to[b].count(a)) to_merge.push(mp(a, b));
	}
	void merge(int a, int b) {
//		cerr << "MERGE: " << a << ' ' << b << '\n';
		assert(a == get(a) && b == get(b));
		if (a == b) return;
		res += (ll)sz(a)*(ll)ssize(c[b])+(ll)sz(b)*(ll)ssize(c[a]);
		if (all_sz(a) > all_sz(b)) swap(a, b);
		for (int x : c[a]) {
			if (c[b].count(x)) res -= sz(a)+sz(b);
			else c[b].insert(x);
		}
		to[a].erase(b); to[b].erase(a);
		for (int x : to[a]) {
			if (to[b].count(x)) continue;
			addEdge(b, x);
		}

		e[b] += e[a];
		e[a] = b;
	}
	void add(int a, int b) {
		b = get(b);
		if (get(a) != b && !c[b].count(a)){
			c[b].insert(a);
			res += sz(b);
			a = get(a);
			addEdge(a, b);
			while (to_merge.size() > 0) {
				pair<int, int> p = to_merge.front();
				to_merge.pop();
				merge(p.fi, p.se);
			}
		}
	}
};

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

	int n, m;
	cin >> n >> m;
	UF u(n);
	REP(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		u.add(a, b);	
		cout << u.res << '\n';
	}

	return 0;
}

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