Submission #618882

#	Time	Username	Problem	Language	Result	Execution time	Memory
618882		errorgorn	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	13 ms	23764 KiB

joitter2

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m;

int p[10005];
int s[100005];

int par(int i){
	if (p[i]==i) return i;
	else return p[i]=par(p[i]);
}

set<ii> al[100005]; //point out
set<int> al2[100005]; //point in
int num[100005]; //number of edges pointing into

int IDX=0;
set<int> id[300005]; //id of those guys in the equiv class who are pointing

vector<ii> proc;

int get(int A,int B){
	auto it=al[A].lb(ii(B,-1));
	if (it==al[A].end() || (*it).fi!=B) return -1;
	else return (*it).se;
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>m;
	
	rep(x,1,n+1){
		p[x]=x;
		s[x]=1;
	}
	
	int a,b;
	int ans=0;
	while (m--){
		cin>>a>>b;
		int A=par(a),B=par(b);
		
		if (A!=B){
			if (get(A,B)==-1) al[A].insert({B,IDX++});
			
			auto it=al[A].lb(ii(B,-1));
			int idx=(*it).se;
			if (!id[idx].count(a)){
				id[idx].insert(a);
				num[B]++;
				ans+=s[B];
			}
			
			if (get(B,A)!=-1) proc.pub({A,B});
		}
		
		while (!proc.empty()){
			tie(A,B)=proc.back(); proc.pob();
			A=par(A),B=par(B);
			if (A==B) continue;
			
			if (sz(al[A])+sz(al2[A])>sz(al[B])+sz(al2[B])) swap(A,B);
			
			//update proc in case of more mergers
			for (auto [it,idx]:al[A]) if (get(it,B)!=-1) proc.pub({A,it});
			for (auto it:al2[A]) if (get(B,it)!=-1) proc.pub({A,it});
			
			ans-=num[A]*s[A]+num[B]*s[B];
			ans-=s[A]*(s[A]-1)+s[B]*(s[B]-1);
			
			//erase same edges
			int idx=get(A,B);
			al[A].erase({B,idx});
			al2[B].erase(A);
			num[B]-=sz(id[idx]);
			
			idx=get(B,A);
			al[B].erase({A,idx});
			al2[A].erase(B);
			num[A]-=sz(id[idx]);
			
			for (auto [it,idx]:al[A]){
				int idx2=get(B,it);
				al2[it].erase(A);
				
				if (idx2==-1){
					al[B].insert({it,idx});
					al2[it].insert(B);
				}
				else{
					if (sz(id[idx2])<sz(id[idx])) swap(id[idx2],id[idx]);
					for (auto it:id[idx]) id[idx2].insert(it);
				}
			}
			for (auto it:al2[A]){
				int idx=get(it,A);
				int idx2=get(it,B);
				num[B]+=sz(id[idx]);
				if (idx2==-1){
					al[it].insert({B,idx});
					al2[B].insert(it);
				}
				else{
					if (sz(id[idx2])<sz(id[idx])) swap(id[idx2],id[idx]);
					for (auto it:id[idx]){
						if (id[idx2].count(it)) num[B]--;
						else id[idx2].insert(it);
					}
				}
			}
			
			s[B]+=s[A];
			ans+=num[B]*s[B];
			ans+=s[B]*(s[B]-1);
			
			p[A]=B;
		}
		
		//rep(x,1,n+1) cout<<p[x]<<" "; cout<<endl;
		//rep(x,1,n+1) cout<<s[x]<<" "; cout<<endl;
		//rep(x,1,n+1) cout<<num[x]<<" "; cout<<endl;
		cout<<ans<<endl;
	}
}

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