제출 #724148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
724148		badont	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	1 ms	212 KiB

joitter2

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <cmath>
#include <utility>
#include <numeric>
using namespace std;

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 << "]";
}
 
 
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
 
//var 
ll T;
 
struct DSU {
	int n;
	vector<int> par, siz;
	vector<set<int>> outgoing, incoming, hitting;
  vector<pii> to_onion;
 
	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), hitting(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 one_way(int a, int b) {
    assert (a == fnd(a) and b == fnd(b));
    outgoing[a].insert(b);
    incoming[b].insert(a);
    
    if (incoming[a].count(b)) {
      to_onion.pb({a, b});
    }
  }
 
	void onion(int a, int b) {
		a = fnd(a), b = fnd(b);
		if (a == b) return;
 
		int sa = (int)outgoing[a].size() + (int)incoming[a].size() + (ll)hitting[a].size();
		int sb = (int)outgoing[b].size() + (int)incoming[b].size() + (ll)hitting[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)hitting[a].size();
		running_ans -= (ll)siz[b] * (ll)hitting[b].size();

    for (auto u : hitting[a]) {
      assert(fnd(u) != a);
      if (fnd(u) != b) {
        hitting[b].insert(u);
      }
    }
 
		running_ans -= C2(siz[a]) + C2(siz[b]);
		for (auto u : incoming[a])  {
			outgoing[u].erase(a);
			if (fnd(u) != b and fnd(u) != a) {
        one_way(u, b);
			}
		}	
 
		for (auto u : outgoing[a]) {
			incoming[u].erase(a);
			if (fnd(u) != b and fnd(u) != a) {
        one_way(b, u);
			}
		}

    incoming[b].erase(a);
    outgoing[b].erase(a);
    incoming[a].erase(b);
    outgoing[a].erase(b);
    hitting[a].erase(b);
    hitting[b].erase(a);
 
		par[a] = b;
		siz[b] += siz[a];
		running_ans += (ll)siz[b] * (ll)hitting[b].size();
		running_ans += C2(siz[b]);
		incoming[a].clear();
		outgoing[a].clear();
    hitting[a].clear();
	}
 
	void add_edge(int a, int b) {
		b = fnd(b);
    if (fnd(a) == fnd(b)) return;

    running_ans -= (ll)siz[b] * (ll)hitting[b].size();
    hitting[b].insert(a);
    running_ans += (ll)siz[b] * (ll)hitting[b].size();

    a = fnd(a);
    one_way(a, b);

    while (!to_onion.empty()) {
      auto [x, y] = to_onion.back();
      to_onion.pop_back();
      onion(x, y);
    }
	}
};
 
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);
 
    #ifdef LOCAL
    cout << "answer: ";
    #endif
		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