Submission #878400

#	Time	Username	Problem	Language	Result	Execution time	Memory
878400		amirhoseinfar1385	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	375 ms	43088 KiB

joitter2

#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