Submission #1026586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026586		Gray	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	576 ms	68436 KiB

joitter2

// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <algorithm>
#include <climits>
#include <ios>
#include<iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#define ll long long
#define ff first
#define ss second
#define ull unsigned ll
#define ln "\n"
#define pll pair<ll, ll>
#define INF 2e18
using namespace std;

struct DSU{
	vector<set<ll>> h_in, h_out, lead;
	vector<ll> par, sz;
	ll n, ecnt;
	DSU(ll N){
		n=N;
		ecnt=0;
		par.resize(n+1, -1);
		h_in=h_out=lead = vector<set<ll>>(n+1);
		for (ll i=1; i<=n; i++) lead[i].insert(i);
		sz.resize(n+1, 1);
	}
	void debug(){
		return;
		for (ll i=1; i<=n; i++){
			cout << i << "::\n";
			cout << "lead: ";
			for (auto ch:lead[i]) cout << ch << ' ';
			cout << "\nin: ";
			for (auto ch:h_in[i]) cout << ch << ' ';
			cout << "\nout: ";
			for (auto ch:h_out[i]) cout << ch << ' ';
			cout << ln << ln;
		}
	}
	queue<pair<ll, ll>> unity;
	ll get(ll u){
		return par[u]==-1?u:par[u]=get(par[u]);
	}

	void bind(ll pu, ll pv){
		h_in[pv].insert(pu);
		h_out[pu].insert(pv);
		if (h_out[pv].count(pu)){
			unity.push({pu, pv});
		}
	}
	void link(ll u, ll v){
		ll pu = get(u), pv=get(v);
		if (pu==pv or lead[pv].count(u)){
			return;
		}else{
			lead[pv].insert(u);
			ecnt+=sz[pv];
			bind(pu, pv);
			proc_unities();
		}
		// debug();
	}
	void unite(ll u, ll v){
		u=get(u); v=get(v);
		if (u==v) return;
		if (h_in[u].size()+h_out[u].size()+lead[u].size()<h_in[v].size()+h_out[v].size()+lead[v].size()) swap(u, v);
		par[v]=u;
		// cout << "PDEB: " << ecnt << ":" << sz[u] << ' ' << sz[v] << ln;
		ecnt+=sz[u]*lead[v].size()+sz[v]*lead[u].size();
		sz[u]+=sz[v];
		// cout << "Unite: " << v << "->" << u << ln;
		// cout << "PDEB: " << ecnt << ln;
		for (auto mem:lead[v]){
			ecnt-=sz[u]*lead[u].count(mem);
			lead[u].insert(mem);
		}
		lead[v].clear();
		h_in[v].erase(u); h_out[u].erase(v);
		h_in[u].erase(v); h_out[v].erase(u);
		for (auto mem:h_in[v]){
			h_out[mem].erase(v);
			bind(mem, u);
		}
		h_in[v].clear();
		for (auto mem:h_out[v]){
			h_in[mem].erase(v);
			bind(u, mem);
		}
		h_out[v].clear();
	}
	void proc_unities(){
		while (!unity.empty()){
			auto cur = unity.front();
			unity.pop();
			unite(cur.ff, cur.ss);
		}
	}
};

void solve(){
	ll n, m; 
	cin >> n >> m;
	DSU tr(n);
	for (ll i=0; i<m; i++){
		ll u, v; cin >> u >> v;
		tr.link(u, v);
		cout << tr.ecnt << ln;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	ll t=1;
	// cin >> t;
	while (t--) {
		solve();
	}
}

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