Submission #1171348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171348		pinbu	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	1454 ms	97156 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int par[N], sz[N]; int findp(int u) {return u ^ par[u] ? par[u] = findp(par[u]) : u;}

int n, m;
set<int> sout[N], g[N], gg[N];
set<array<int, 2>> s1[N], s2[N];
queue<array<int, 2>> qu;

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    cin >> n >> m;
    iota(par + 1, par + 1 + n, 1);
    fill(sz + 1, sz + 1 + n, 1);
    long long ans = 0;
    while (m--) {
    	int uwu, vwv; cin >> uwu >> vwv;
    	qu.push({uwu, vwv});
		while (qu.size()) {
			auto [u, v] = qu.front();
			qu.pop();
			int r1 = findp(u), r2 = findp(v);
			if (r1 ^ r2) {
		    	if (g[r2].find(r1) != g[r2].end()) {
		    		ans += 2LL * sz[r1] * sz[r2] - 1LL * sz[r1] * sout[r1].size() - 1LL * sz[r2] * sout[r2].size();
		    		auto totsz = [&] (int r) {
		    			return s1[r].size() + s2[r].size();
		    		};
		    		if (totsz(r1) < totsz(r2)) swap(r1, r2);
		    		
		    		g[r2].erase(r1); gg[r1].erase(r2);
		    		for (auto [a, b]: s1[r2]) {
		    			if (findp(b) ^ r1) {
		    				sout[r1].insert(b);
		    				s1[r1].insert({a, b});
		    				int rr = findp(b);
		    				g[rr].erase(r2); gg[r2].erase(rr);
		    				g[rr].insert(r1); gg[r1].insert(rr);
		    				qu.push({b, a});
		    			} else {
		    				s2[r1].erase({b, a});
		    			}
		    		}
		    		for (auto [a, b]: s2[r2]) {
		    			if (findp(b) ^ r1) {
		    				s2[r1].insert({a, b});
		    				int rr = findp(b);
		    				g[r2].erase(rr); gg[rr].erase(r2);
		    				g[r1].insert(rr); gg[rr].insert(r1);
		    				qu.push({a, b});
		    			} else {
		    				s1[r1].erase({b, a});
		    				sout[r1].erase(a);
		    			}
		    		}
		    		ans += 1LL * sout[r1].size() * (sz[r1] + sz[r2]);
		    		sz[r1] += sz[r2];
		    		par[r2] = r1;
		    	} else if (sout[r2].find(u) == sout[r2].end()) {
		    		g[r1].insert(r2); gg[r2].insert(r1);
		    		sout[r2].insert(u);
		    		s1[r2].insert({v, u});
		    		s2[r1].insert({u, v});
		    		ans += sz[r2];
		    	}
			}
		}
    	cout << ans << '\n';
    }
    
    return 0;
}
// What a damn and hateful problem!

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