oj.uz

Submission #691900

# Submission time Handle Problem Language Result Execution time Memory
691900 2023-01-31T22:44:41 Z NK_ Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 0 ms 212 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())

using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, M; cin >> N >> M;

	vector<int> ID(N);
	vector<set<int>> G(N), F(N);

	ll ans = 0;

	auto merge = [&](int u, int v) {
		int gu = ID[u], gv = ID[v];

		// cout << "MERGING: " << gu << " " << gv << nl;

		// cout << "BEF: " << nl;

		// cout << "GU: ";
		// for(auto x : G[gu]) cout << x << " ";
		// cout << nl;

		// cout << "FU: ";
		// for(auto x : F[gu]) cout << x << " ";
		// cout << nl;

		// cout << "GV: ";
		// for(auto x : G[gv]) cout << x << " ";
		// cout << nl;

		// cout << "FV: ";
		// for(auto x : F[gv]) cout << x << " ";
		// cout << nl;

		ans -= (sz(F[gu]) - 1) * 1LL * sz(G[gu]);
		ans -= (sz(F[gv]) - 1) * 1LL * sz(G[gv]);

		if (sz(G[gu]) < sz(G[gv])) swap(gu, gv);
		for(const auto &x : G[gv]) {
			ID[x] = gu;
			G[gu].insert(x);
		}	

		if (sz(F[gu]) < sz(F[gv])) F[gu].swap(F[gv]);
		for(const auto &x : F[gv]) F[gu].insert(x);

		int gx = ID[u];
		ans += (sz(F[gx]) - 1) * sz(G[gx]);

		// cout << "AFT: " << gx << nl;

		// cout << "G: ";
		// for(auto x : G[gx]) cout << x << " ";
		// cout << nl;

		// cout << "F: ";
		// for(auto x : F[gx]) cout << x << " ";
		// cout << nl;
	};

	for(int i = 0; i < N; i++) {
		ID[i] = i;
		G[i] = F[i] = {i};
	}

	for(int i = 0; i < M; i++) {
		int u, v; cin >> u >> v; --u, --v; // u follows v
		int gu = ID[u], gv = ID[v];


		if (gu == gv) cout << ans << nl; // Already same group
		else if (F[gv].count(u)) cout << ans << nl; // Already fan of group
		else if (F[gu].count(v)) { // Merge groups + fans
			merge(u, v);
			cout << ans << nl;
		} else { 
			F[gv].insert(u);	
			ans += sz(G[gv]);
			cout << ans << nl;
		}
	}
	
    return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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