Submission #1020081

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

joitter2

#include <ios>
#include<iostream>
#include <queue>
#include <set>
#include <vector>

#define ll long long
#define ff first
#define ss second
#define ull unsigned ll
#define ln "\n"
#define pll pair<ll, ll>

using namespace std;

struct DSU{
	vector<ll> p;
	vector<multiset<ll>> in, out, mem;
	queue<pair<ll, ll>> links;
	ll pedge;
	DSU(ll N){
		p.resize(N+1, -1);
		in.resize(N+1);
		out.resize(N+1);
		mem.resize(N+1);
		for (ll i=1; i<=N; i++) mem[i].insert(i);
		pedge=0;
	}
	ll get(ll x){
		return p[x]==-1?x:p[x]=get(p[x]);
	}
	void unite(ll u, ll v){
		if (in[u].size()+out[u].size()+mem[u].size()<in[v].size()+out[v].size()+mem[v].size()) swap(u, v);
		// cout << "Unity: " << u << " " << v << ln;
		// cout << "Pre: " << pedge << ln;
		p[v]=u;
		pedge+=mem[u].size()*mem[v].size()*2+in[u].size()*mem[v].size();
		for (auto ind:in[v]){
			pedge-=mem[v].size();
			out[ind].erase(out[ind].find(v));
			link(ind, u);
		}
		in[v].clear();
		for (auto outd:out[v]){
			pedge-=mem[outd].size();
			in[outd].erase(in[outd].find(v));
			link(outd, u);
		}
		out[v].clear();
		for (auto child:mem[v]){
			mem[u].insert(child);
		}
		mem[v].clear();
		// cout << "Post: " << pedge << ln;

	}
	void follow(ll u, ll v){
		link(u, v);
		while (!links.empty()){
			unite(links.front().ff, links.front().ss);
			links.pop();
		}
		// cout << "end\n";
	}
	void link(ll u, ll v){
		// cout << "Linking: " << u << " - " << v << ln;
		u=get(u);
		v=get(v);
		if (out[u].find(v)!=out[u].end()) return;
		if (u==v) return;
		if (out[v].find(u)!=out[v].end()){
			pedge-=mem[u].size()*out[v].count(u);
			out[v].erase(u);
			in[u].erase(v);
			links.push({u, v});
			return;
		}else{
			pedge+=mem[v].size();
			out[u].insert(v);
			in[v].insert(u);
		}
	}
};

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.follow(u, v);
		cout << tr.pedge << ln;
	}
}

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

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