oj.uz

Submission #911177

# Submission time Handle Problem Language Result Execution time Memory
911177 2024-01-18T14:40:21 Z mickey080929 Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 4 ms 14940 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

ll par[100010];
ll sz[100010];
set<ll> in[100010], out[100010], all[100010];

ll Find(ll x) {
	if (x == par[x]) return x;
	return par[x] = Find(par[x]);
}

ll ans = 0;
vector<pll> mrg;

void add_edge(ll u, ll v) {
	in[v].insert(u);
	if (in[u].count(v)) mrg.push_back({u, v});
}

void Union(ll x, ll y) {
	x = Find(x);
	y = Find(y);
	if (x == y) return;
	if (all[x].size() < all[y].size()) swap(x, y);
	ans += all[x].size() * sz[y] + all[y].size() * sz[x];
	sz[x] += sz[y];
	par[y] = x;
	for (auto &v : all[y]) {
		if (all[x].count(v)) ans -= sz[x];
		else all[x].insert(v);
	}
	in[y].erase(x); in[x].erase(y);
	for (auto &v : in[y]) {
		add_edge(v, x);
	}
}

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	ll N, M;
	cin >> N >> M;
	for (ll i=1; i<=N; i++) {
		par[i] = i;
		sz[i] = 1;
		all[i].insert(i);
	}
	for (ll i=0; i<M; i++) {
		ll u, v;
		cin >> u >> v;
		v = Find(v);
		if (all[v].count(u)) {
			cout << ans << '\n';
			continue;
		}
		all[v].insert(u);
		ans += sz[v];
		u = Find(u);
		add_edge(u, v);
		while (!mrg.empty()) {
			auto t = mrg.back();
			mrg.pop_back();
			Union(t.first, t.second);
		}
		cout << ans << '\n';
	}
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Incorrect 4 ms 14940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Incorrect 4 ms 14940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Incorrect 4 ms 14940 KB Output isn't correct
4 Halted 0 ms 0 KB -