Submission #365316

#	Time	Username	Problem	Language	Result	Execution time	Memory
365316		negar_a	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1467 ms	96748 KiB

joitter2

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

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <ll, ll>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const ll maxn = 3e5 + 10;
ll par[maxn], sz[maxn];
set <ll> in[maxn], inc[maxn];
set <pii> out[maxn];
queue <pii> q;
ll ans = 0;

ll find_par(ll x){
	if(x == par[x])
		return x;
	return par[x] = find_par(par[x]);
}
inline bool add_edge(ll a, ll b){
	b = find_par(b);
	ll p = find_par(a);
	if(p == b || out[p].find(mp(a, b)) != out[p].end()){
		return false;
	}
	out[p].insert({a, b});
	in[b].insert(a);
	inc[b].insert(p);
	if(inc[p].find(b) != inc[p].end()){
		q.push({p, b});
	}
	return true;
}
void update_edges(ll x, ll y){
	vector <pii> add, del;
	for(ll u : in[x]){
		del.pb({u, x});
		if(find_par(u) != y){
			add.pb({u, y});
		}
	}
	for(auto u : out[x]){
		del.pb(u);
		if(find_par(u.S) != y)
			add.pb(u);
	}
	for(auto u : del){
		out[find_par(u.F)].erase(u);
		in[find_par(u.S)].erase(u.F);
	}
	
	ll px = find_par(x);
	ll py = find_par(y);
	par[px] = py;
	sz[py] += sz[px];
	
	for(auto u : add){
		add_edge(u.F, u.S);
	}
}
ll siz(ll y){
//	cout << "innn " << in[y].size() << endl;
	return 1LL * sz[y] * (sz[y] - (ll)1) + sz[y] * (ll)in[y].size();
}

void merge(ll x, ll y){
	if(in[x].size() + out[x].size() > in[y].size() + out[y].size())
		swap(x, y);
	ans -= (siz(y) + siz(x));
//	cout << "annnnn " << ans << endl;
	update_edges(x, y);
	ans += siz(y);
}

int main(){
	fast_io;
	ll n, m;
	cin >> n >> m;
	for(ll i = 0; i < n; i ++){
		sz[i] = 1;
		par[i] = i;
	}
	while(m --){
		ll a, b;
		cin >> a >> b;
		a --; b --;
		if(add_edge(a, b)){
			ans += sz[find_par(b)];
		}
		while(q.size()){
			ll x = find_par(q.front().F);
			ll y = find_par(q.front().S);
//			cout << "!: " << x << " " << y << endl;
			q.pop();
			if(x != y){
				merge(x, y);
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

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