제출 #878396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878396		amirhoseinfar1385	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	363 ms	40984 KiB

joitter2

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4")
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int n,m; 

struct dsu{
	int par[maxn],sz[maxn];
	set<pair<int,int>>kho[maxn];
	set<int>vorod[maxn];
	long long res;
	dsu(){
		res=0;
		for(int i=1;i<maxn;i++){
			par[i]=i;
			sz[i]=1;
		}
	}
	int root(int u){
		if(u==par[u]){
			return u;
		}
		return par[u]=root(par[u]);
	}

	void con(int u,int v){
		u=root(u),v=root(v);
		if(sz[u]>sz[v]){
			swap(u,v);
		}
		vector<pair<int,int>>allq;
		for(auto x:kho[u]){
			res-=sz[x.first];
			vorod[x.first].erase(x.second);
			allq.push_back(make_pair(x.second,x.first));
		}
		res+=sz[u]*(2*sz[v]+vorod[v].size());
		res-=sz[u]*vorod[u].size();
		for(auto x:vorod[u]){
			int rootx=root(x);
			kho[rootx].erase(make_pair(u,x));
			allq.push_back(make_pair(x,u));
		}
		vorod[u].clear();
		kho[u].clear();
		par[u]=v;
		sz[v]+=sz[u];
		for(auto x:allq){
			add(x.first,x.second);
		}
	}
	void add(int u,int v){
		int rootv=root(v),rootu=root(u);
		if(rootu==rootv||vorod[rootv].count(u)!=0){
			return ;
		}
		auto x=kho[rootv].lower_bound(make_pair(rootu,-1));
		if(x!=kho[rootv].end()&&(*x).first==rootu){
			return con(u,v);
		}
		res+=sz[rootv];
		kho[rootu].insert(make_pair(rootv,u));
		vorod[rootv].insert(u);
	}
}ds;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		ds.add(u,v);
		cout<<ds.res<<"\n";
	}	
}

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