Submission #723631

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

joitter2

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

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
ll T;

struct DSU {
	int n;
	vector<int> par, siz;
	vector<set<int>> outgoing, incoming;

	ll running_ans = 0;

	// inductively assuming it's up to date already
	// choose smallest outgoing + incoming size?
	// insert all incoming that aint from big boy into big boy
	// change all outgoing to new big boy	
		// delete outgoing if it goes into big boy

	DSU (int n) : n(n), par(n), siz(n, 1), outgoing(n), incoming(n), running_ans(0) {
		iota(all(par), 0);
	};

	int fnd(int g) {
		if (g == par[g]) return g;
		return par[g] = fnd(par[g]);
	}	

	void onion(int a, int b) {
		a = fnd(a), b = fnd(b);
		assert (a != b);

		int sa = (int)outgoing[a].size() + (int)incoming[a].size();
		int sb = (int)outgoing[b].size() + (int)incoming[b].size();

		if (sa > sb) {
			swap(a, b);
			swap(sa, sb);
		}

		auto C2 = [&](ll x) -> ll {
			return ((x) * (x - 1));
		};

		running_ans -= (ll)siz[a] * (ll)incoming[a].size();
		running_ans -= (ll)siz[b] * (ll)incoming[b].size();

		par[a] = b;

		running_ans -= C2(siz[a]) + C2(siz[b]);

		/*
		for (auto u : incoming[a])  {
			outgoing[u].erase(a);
			if (fnd(u) != b) {
				assert(fnd(u) != a);
				outgoing[u].insert(b);
				incoming[b].insert(u);
			}
		}	
		for (auto u : outgoing[a]) {
			incoming[u].erase(a);
			if (fnd(u) != b) {
				assert(fnd(u) != a);
				outgoing[b].insert(u);
				incoming[u].insert(b);
			}
		}
		incoming[b].erase(a);
		outgoing[b].erase(a);
		*/
		set<int> new_incoming, new_outgoing;
		for (auto u : incoming[a]) if (fnd(u) != a and fnd(u) != b) {
			assert (u == fnd(u));
			new_incoming.insert(u);
		}
		for (auto u : incoming[b]) if (fnd(u) != a and fnd(u) != b) {
			assert (u == fnd(u));
			new_incoming.insert(u);
		}
		for (auto u : outgoing[a]) if (fnd(u) != a and fnd(u) != b) {
			assert (u == fnd(u));
			new_outgoing.insert(u);
		}
		for (auto u : outgoing[b]) if (fnd(u) != a and fnd(u) != b) {
			assert (u == fnd(u));
			new_outgoing.insert(u);
		}

		swap(incoming[b], new_incoming);
		swap(outgoing[b], new_outgoing);
		siz[b] += siz[a];
		running_ans += (ll)siz[b] * (ll)incoming[b].size();
		running_ans += C2(siz[b]);
		incoming[a].clear();
		outgoing[a].clear();
		siz[a] = 0;
	}

	void add_edge(int a, int b) {
		a = fnd(a), b = fnd(b);
		if (a == b) return;
		
		running_ans -= (ll)siz[b] * (ll)incoming[b].size();
		outgoing[a].insert(b);
		incoming[b].insert(a);
		running_ans += (ll)siz[b] * (ll)incoming[b].size();

		if (outgoing[b].count(a)) {
			assert(incoming[a].count(b));
			onion(a, b);	
			return;
		}
	}
};

void solve() {
	int n, m;
	cin >> n >> m;

	DSU dsu(n);
	while (m--) {
		ll x, y;
		cin >> x >> y;
		x--; y--;

		dsu.add_edge(x, y);

		cout << dsu.running_ans << "\n";
	}
	
}

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

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

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