oj.uz

Submission #981370

# Submission time Handle Problem Language Result Execution time Memory
981370 2024-05-13T06:15:27 Z happy_node Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 5 ms 10072 KB 
#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];

	return true;
}

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;

			assert(st[find(a)].count(b));
			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';
	}
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10072 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10072 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10072 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -