oj.uz

Submission #834728

# Submission time Handle Problem Language Result Execution time Memory
834728 2023-08-22T17:50:41 Z ToniB Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 6 ms 15188 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 : out[u]){
		if(edge[x][v] && f(x) != v) nxt = x;
	}
	for(int x : in[u]){
		if(edge[v][x] && f(x) != v) nxt = x;
		edge[x][v] = 1;
	}
	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(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	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) continue;
		bool exist = 0;
		for(int x : out[fv]){
			if(f(x) == fu) exist = 1;
		}
		if(exist){
			join(fu, fv);
		} else {
			bool exist = 0;
			for(int j = 0; j < n; ++j){
				if(f(j) == fv && edge[u][j]) exist = 1;
			}
			if(!exist){
				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

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 15188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 15188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 15188 KB Output isn't correct
2 Halted 0 ms 0 KB -