Submission #311799

#	Time	Username	Problem	Language	Result	Execution time	Memory
311799		YJU	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	169 ms	197368 KiB

joitter2

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=(1LL<<21);
const ll C=20;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,m,x[N],y[N],sz[N],dir[N],ans;
vector<ll> que[N],rem[N];
map<pll,bool> vis;
set<ll> in[N];

ll f(ll id){return (id==dir[id]?id:dir[id]=f(dir[id]));}

void merge(ll a,ll b){
	a=f(a);b=f(b);
	if(a==b)return;
	if(SZ(in[a])>SZ(in[b]))swap(a,b);
	ans-=(SZ(in[b])+sz[b]-1)*sz[b]+(SZ(in[a])+sz[a]-1)*sz[a];
	sz[b]+=sz[a];sz[a]=0;dir[a]=b;
	while(SZ(in[a])){
		ll tmp=*in[a].begin();
		in[a].erase(in[a].begin());
		in[b].insert(tmp);
	}
	ans+=(SZ(in[b])+sz[b]-1)*sz[b];
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP(i,m)cin>>x[i]>>y[i];
	REP(i,m)que[(1<<(C-1))].pb(i);
	for(int i=C-1;i>=0;i--){
		vis.clear();
		REP1(j,n)dir[j]=j;
		for(ll j=0;j<(1<<C);j++){
			if(x[j]!=0&&y[j]!=0){
				vis[mp(x[j],y[j])]=1;
				if(vis[mp(y[j],x[j])]==1)dir[f(x[j])]=f(y[j]);
			}
			if(i==0){
				if((j&(1<<i))){
					for(auto k:que[j]){
						if(f(x[k])==f(y[k]))rem[j].pb(k);
						else rem[j+1].pb(k);
					}
				}
				continue;
			}
			if((j&(1<<i))&&(j&((1<<i)-1))==0){
				for(auto k:que[j]){
					if(f(x[k])==f(y[k]))que[j-(1<<(i-1))].pb(k);
					else que[j+(1<<(i-1))].pb(k);
				}
			}
		}
	}
	vis.clear();
	REP1(i,n)dir[i]=i,sz[i]=1;
	REP(i,m){
		vis[mp(x[i],y[i])]=1;
		for(ll j:rem[i]){
			if(j>=i)continue;
			ans-=sz[f(y[j])];
			in[f(y[j])].erase(x[j]);
		}
		if(vis[mp(y[i],x[i])]==1){
			merge(x[i],y[i]);
		}else{
			if(in[f(y[i])].find(x[i])==in[f(y[i])].end()&&f(x[i])!=f(y[i])){
				ans+=sz[f(y[i])];
				in[f(y[i])].insert(x[i]);
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

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