제출 #691903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
691903		NK_	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	2310 ms	232764 KiB

joitter2

// 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), FG(N), GF(N);

	ll ans = 0;

	int cur = 0;
	vector<array<int, 2>> MERGE; 

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

		// 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 << "FGU: ";
		// for(auto x : FG[gu]) cout << x << " ";
		// cout << nl;

		// cout << "GF: ";
		// for(auto x : GF[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;

		// cout << "FGV: ";
		// for(auto x : FG[gv]) cout << x << " ";
		// cout << nl;

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

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

		// CHECK FOR OTHER MERGES;

		set<int> add;

		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);

		// if (sz(FG[gu]) < sz(FG[gv])) FG[gu].swap(FG[gv]);
		
		for(const auto &x : GF[gv]) {
			// cout << "SAW: " << x << nl;
			if (GF[x].count(gu)) add.insert(x);
			if (GF[x].count(gv)) add.insert(x);
			GF[gu].insert(x); FG[x].insert(gu);
		}
		

		for(const auto &x : FG[gv]) {
			// cout << "SAW: " << x << nl;
			if (FG[x].count(gu)) add.insert(x);
			if (FG[x].count(gv)) add.insert(x);
			FG[gu].insert(x); GF[x].insert(gu);
		}

		int gx = ID[u];
		ans += (sz(F[gx]) - 1) * 1LL * 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;

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

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

		for(const auto &x : add) {
			if (x == gu || x == gv) continue;
			// cout << "ADDED: " << ID[x] << nl;
			MERGE.push_back({x, gx});
		}
	};

	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 (FG[gv].count(gu)) { // Merge groups + fans
			
			MERGE.push_back({gv, gu});
			while(cur < sz(MERGE)) {
				merge(MERGE[cur][0], MERGE[cur][1]); cur++;
			}

			cout << ans << nl;
		} else { 
			F[gv].insert(u);	
			FG[gu].insert(gv);
			GF[gv].insert(gu);

			ans += sz(G[gv]);
			cout << ans << nl;
		}
	}
	
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83