Submission #1182885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182885		vako_p	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	960 ms	127664 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << " ---> " << x << endl;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int mxN = 1e6 + 5;
ll n,m;

struct ds{
	vector<ll> sz,par,sz1,sz2;
	vector<map<ll, set<ll>>> in,out;
	ll ans = 0;
	
	void init(){
		par.resize(n + 5);
		sz.assign(n + 5, 1LL);
		sz1.assign(n + 5, 0LL);
		sz2.assign(n + 5, 0LL);
		in.resize(n + 5);
		out.resize(n + 5);
		for(int i = 0; i < n + 5; i++) par[i] = i;
	}
	
	ll find(ll at){
		if(at == par[at]) return at;
		par[at] = find(par[at]);
		return par[at];
	}
	
	void merge(ll a, ll b){
		a = find(a);
		b = find(b);
		if(a == b) return;
		if(sz1[a] + sz2[a] < sz1[b] + sz2[b]) swap(a, b);
		ans -= sz[a] * in[b][a].size() + sz[b] * in[a][b].size() - sz[a] * sz[b] * 2;
//		cout << a << ' ' << b << ' ' << ans << '\n';
		sz1[a] -= in[a][b].size();
		sz1[b] -= in[b][a].size();
		sz2[a] -= out[a][b].size();
		sz2[b] -= out[b][a].size();
		in[a][b].clear();
		out[b][a].clear();
		in[b][a].clear();
		out[a][b].clear();
		vector<ll> v;
		for(auto it1 : in[b]){
			for(auto it : it1.sd){
				in[a][it1.ff].insert(it);
				out[it1.ff][b].erase(it);
				out[it1.ff][a].insert(it);
				sz1[a]++;
				if(in[it1.ff][a].size()) v.pb(it1.ff);
			}
		}
		in[b].clear();
		ll cnt = sz2[a],cnt1 = sz2[b];
		for(auto it1 : out[b]){
			for(auto it : it1.sd){
				in[it1.ff][b].erase(it);
				if(in[a][it1.ff].size()) v.pb(it1.ff);
				if(out[a][it1.ff].find(it) != out[a][it1.ff].end()){
					sz1[it1.ff]--; 
					cnt--;
					cnt1--;
				} 
				else{
					in[it1.ff][a].insert(it);
					out[a][it1.ff].insert(it);
					sz2[a]++;
				}
			}
		}
		ans += cnt * sz[b] + cnt1 * sz[a];
		par[b] = a;
		sz[a] += sz[b];
//		cout << "--> " << v.size() << '\n';
		for(auto it : v) merge(a, it);
	}
	
	void sett(ll a, ll b){
		ll p = find(a),p1 = find(b);
		if(p == p1 or out[p1][p].find(a) != out[p1][p].end()) return;
		ans += sz[p1];
		sz1[p]++;
		sz2[p1]++;
		in[p][p1].insert(a);
		out[p1][p].insert(a);
		if(in[p1][p].size()) merge(p, p1);
	}
};

int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	ds s;
	s.init();
	for(int i = 0; i < m; i++){
		ll a,b;
		cin >> a >> b;	
		s.sett(a, b);
		cout << s.ans << '\n';
	}
}

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