Submission #981368

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

joitter2

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

typedef long long ll;
const int MX=1e5+5;
int N,M;

ll par[MX], s[MX];

int find(int v) {
	return par[v]==v?v:par[v]=find(par[v]);
}

set<int> st[MX];
ll ans=0;

bool merge(int u, int v) {
	u=find(u),v=find(v);
	if(u==v) return false;
	if(st[u].size()>st[v].size()) swap(u,v);

	ll c=st[u].size();
	ans-=s[u]*(s[u]-1);
	ans-=c*s[u];
	c=st[v].size();
	ans-=s[v]*(s[v]-1);
	ans-=c*s[v];

	for(auto x:st[u]) {
		st[v].insert(x);
	}
	st[u].clear();
	par[u]=v;
	s[v]+=s[u];
	c=st[v].size();
	ans+=s[v]*(s[v]-1);
	ans+=c*s[v];
}

void prep() {
	for(int i=1;i<=N;i++) {
		par[i]=i;
		s[i]=1;
	}
}

set<pair<int,int>> edges;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N>>M;
	prep();

	for(int i=1;i<=M;i++) {
		int a,b;
		cin>>a>>b;
		
		if(edges.count({b,a})) {
			ll c=st[find(a)].size();
			ans-=s[find(a)]*c;
			st[find(a)].erase(b);
			c=st[find(a)].size();
			ans+=s[find(a)]*c;
			merge(a,b);
		} else {
			ll c=st[find(b)].size();
			ans-=s[find(b)]*c;
			st[find(b)].insert(a);
			c=st[find(b)].size();
			ans+=s[find(b)]*c;
		}

		edges.insert({a,b});

		cout<<ans<<'\n';
	}
}

Compilation message (stderr)

joitter2.cpp: In function 'bool merge(int, int)':
joitter2.cpp:37:5: warning: control reaches end of non-void function [-Wreturn-type]
   37 |  ans+=c*s[v];
      |  ~~~^~~~~~~~

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