Submission #982751

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

joitter2

#include <bits/stdc++.h>

#define ll int
#define ld long double
#define ff first
#define ss second
#define ln "\n"

using namespace std;

const ll INF = INT_MAX;

struct DSU{
	struct Vertex{
		set<ll> in, out, foll;
		ll sz;
		ll size(){
			return foll.size();
		}
	};
	ll cnt, sz;
	vector<Vertex> a;
	queue<pair<ll, ll>> unity;
	vector<ll> p;
	DSU(ll N){
		a.resize(N+1);
		sz=N;
		for (ll i=1; i<=sz; i++){
			a[i].sz=1;
			a[i].foll.insert(i);
		}
		p.resize(N+1, -1);
		cnt=0;
	}
	ll get(ll x){
		return p[x]==-1?x:p[x]=get(p[x]);
	}
	void merge(ll pu, ll pv){
		a[pv].in.insert(pu);
		a[pu].out.insert(pv);
		if (a[pu].in.count(pv)){
			unity.push({pu, pv});
		}
	}
	void unite(ll u, ll v){
		u = get(u);	v = get(v);
		if (u==v) return;
		if (a[u].size()<a[v].size()){
			swap(u, v);
		}
		// cout << u << "-" << v << " -- " << cnt << ln;
		cnt+=a[u].sz*a[v].foll.size()+a[v].sz*a[u].foll.size();
		// cout << cnt << ln;
		for (auto fol:a[v].foll){
			if (a[u].foll.count(fol)) cnt-=a[u].sz+a[v].sz;
			else{
				a[u].foll.insert(fol);
			}
		}
		// cout << cnt << ln;
		a[u].in.erase(v);
		a[u].out.erase(v);
		a[v].in.erase(u);
		a[v].out.erase(u);
		p[v]=u;
		a[u].sz+=a[v].sz;
		for (auto out:a[v].out){
			a[out].in.erase(v);
			merge(v, out);
		}
		for (auto ind:a[v].in){
			a[ind].out.erase(v);
			merge(ind, u);
		}
	}
	void link(ll u, ll v){
		ll pu = get(u), pv = get(v);
		if (pu!=pv and !a[pv].in.count(u)){
			a[pv].foll.insert(u);
			cnt+=a[pv].sz;
			// cout << u << "-" << v << ":" <<  cnt << ln;
			merge(pu, pv);
			while (!unity.empty()){
				unite(unity.front().ff, unity.front().ss);
				unity.pop();
			}
		}
	}
};

void solve(){
	ll n, m; cin >> n >> m;
	DSU tree(n);
	while (m--){
		ll u, v; cin >> u >> v;
		tree.link(u, v);
		cout << tree.cnt << endl;
	}
}


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

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