oj.uz

답안 #981377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981377 2024-05-13T06:22:29 Z happy_node 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 1 ms 4956 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(find(a)!=find(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';
	}
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -