Submission #933884

#	Time	Username	Problem	Language	Result	Execution time	Memory
933884		moonrabbit2	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	6 ms	20060 KiB

joitter2

#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
const ll mod=1000000007;
const int N=100005;
int n,m;
struct UF{
	int p[N];
	ll ans=0,sz[N];
	set<int> in[N],out[N],inV[N],S[N];
	void init(){
		for(int i=1;i<=n;i++){
			p[i]=0;
			sz[i]=1;
			S[i].emplace(i);
		}
	}
	int Find(int u){
		if(!p[u]) return u;
		return p[u]=Find(p[u]);
	}
	void add(int u,int v){
		int Gu=Find(u),Gv=Find(v);
		if(Gu==Gv) return;
		if(in[Gu].count(Gv)){
			ans+=2*sz[Gu]*sz[Gv];
			ans-=sz[Gu]*inV[Gu].size();
			ans-=sz[Gv]*inV[Gv].size();
			//debug(sz[Gu],sz[Gv],inV[Gu],inV[Gv]);
			if(in[Gu].size()+out[Gu].size()+inV[Gu].size()+S[Gu].size()<in[Gv].size()+out[Gv].size()+inV[Gv].size()+S[Gv].size()) swap(Gu,Gv);
			vector<int> V1,V2;
			for(int Gw: in[Gv]){
				out[Gw].erase(Gv);
				out[Gw].emplace(Gu);
				in[Gu].emplace(Gw);
				if(out[Gu].count(Gw)) V1.emplace_back(Gw);
			}
			for(int Gw: out[Gv]){
				in[Gw].erase(Gv);
				in[Gw].emplace(Gu);
				out[Gu].emplace(Gw);
				if(in[Gu].count(Gw)) V2.emplace_back(Gw);
			}
			for(int w: inV[Gv]){
				if(!S[Gu].count(w)) inV[Gu].emplace(w);
			}
			for(int w: S[Gv]){
				S[Gu].emplace(w);
				inV[Gu].erase(w);
			}
			sz[Gu]+=sz[Gv];
			ans+=sz[Gu]*inV[Gu].size();
			//debug(sz[Gu],inV[Gu]);
			p[Gv]=Gu;
			for(int Gw: V1) add(Gu,Gw);
			for(int Gw: V2) add(Gw,Gu);
		} else if(!in[Gv].count(u)){
			ans+=sz[Gv];
			//debug(sz[Gv]);
			in[Gv].emplace(Gu);
			out[Gu].emplace(Gv);
			inV[Gv].emplace(u);
		}
	}
}U;
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	U.init();
	for(int u,v,i=1;i<=m;i++){
		cin>>u>>v;
		U.add(u,v);
		cout<<U.ans<<"\n";
	}
	return 0;
}

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