oj.uz

답안 #834645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834645 2023-08-22T16:26:34 Z ToniB 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 7 ms 15108 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 2;

int n, m, uf[MAXN], sz[MAXN], cnt_inside[MAXN];
ll ans;
set<int> in[MAXN], out[MAXN];
unordered_map<int, bool> edge[MAXN];

int f(int x){
	while(uf[x] != -1) x = uf[x];
	return x;
}

void merge_set(set<int>& a, set<int>& b){
	if(a.size() > b.size()) swap(a, b);
	for(int x : a) b.insert(x);
}

void join(int u, int v){
	ans += 2LL * sz[u] * sz[v];
	ans -= (ll)sz[u] * (in[u].size() - cnt_inside[u]) + (ll)sz[v] * (in[v].size() - cnt_inside[v]);
	if(out[u].size() + in[u].size() > out[v].size() + in[v].size()) swap(u, v);
	int nxt = -1;
	for(int x : in[u]){
		edge[x][v] = 1;
		if(edge[v][x] && f(x) != v) nxt = x;
	}
	for(int x : out[u]){
		if(edge[x][v] && f(x) != v) nxt = x;
	}

	for(int x : out[u]){
		if(f(x) == v) ++cnt_inside[v];
	}
	for(int x : in[u]){
		if(f(x) == v) ++cnt_inside[v];
	}

	merge_set(out[u], out[v]);
	merge_set(in[u], in[v]);

	uf[u] = v;
	sz[v] += sz[u];
	cnt_inside[v] += cnt_inside[u];
	
	ans += (ll)sz[v] * (in[v].size() - cnt_inside[v]);
	
	if(nxt != -1) join(f(nxt), v);
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < n; ++i) uf[i] = -1, sz[i] = 1;

	for(int i = 0; i < m; ++i){
		int u, v; cin >> u >> v, --u, --v;
		int fu = f(u), fv = f(v);
		if(fu == fv){
			++cnt_inside[fu];
			in[fu].insert(fu);
			out[fu].insert(fu);
			continue;
		}
		bool exist = 0;
		for(int x : out[fv]){
			if(f(x) == fu) exist = 1;
		}
		if(exist){
			join(fu, fv);
		} else {
			if(!edge[u][fv]){
				edge[u][fv] = 1;
				ans += sz[fv];
			}
			in[fv].insert(u);
			out[fu].insert(v);
		}
		
		cout << ans << "\n";
	}
	
	return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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