Submission #1171345

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

joitter2

#include <bits/stdc++.h>
#define int long long
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);
    // for (int i = 1; i <= n; i++) {
    	// cc[i].insert(i);
    // }
    // cout << '\n';
    int ans = 0;
    while (m--) {
    	int uwu, vwv; cin >> uwu >> vwv;
    	qu.push({uwu, vwv});
		while (qu.size()) {
			auto [u, v] = qu.front();
			// cerr << "#" << m << ' ' << u << ' ' << v << '\n';
			qu.pop();
			int r1 = findp(u), r2 = findp(v);
			if (r1 ^ r2) {
		    	if (g[r2].find(r1) != g[r2].end()) {
		    		ans += 2 * sz[r1] * sz[r2] - sz[r1] * sout[r1].size() - sz[r2] * sout[r2].size();
		    		auto totsz = [&] (int r) {
		    			return s1[r].size() + s2[r].size();
		    		};
		    		if (totsz(r1) < totsz(r2)) swap(r1, r2);
		    		vector<array<int, 2>> vt;
		    		for (auto [a, b]: s1[r2]) {
		    			if (findp(b) ^ r1) {
		    				// cerr << "?\n";
		    				sout[r1].insert(b);
		    				s1[r1].insert({a, b});
		    				int rr = findp(b);
		    				vt.push_back({rr, r2});
		    				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);
		    				vt.push_back({r2, rr});
		    				qu.push({a, b});
		    			} else {
		    				s1[r1].erase({b, a});
		    				sout[r1].erase(a);
		    				// cerr << "? " << b << '\n';
		    			}
		    		}
		    		// for (int nu: cc[r2]) {
		    			// cc[r1].insert(nu);
		    			// if (sout[r1].find(nu) != sout[r1].end()) {
		    				// sout[r1].
		    			// }
		    		// }
		    		// if (u == 2 && v == 1) cerr << *sout[r1].begin() << '\n';
		    		ans += sout[r1].size() * (sz[r1] + sz[r2]);
		    		sz[r1] += sz[r2];
		    		par[r2] = r1;
		    		g[r2].erase(r1); gg[r1].erase(r2);
		    		for (auto p: vt) {
		    			auto [ra, rb] = p;
		    			g[ra].erase(rb); gg[rb].erase(ra);
		    			ra = findp(ra); rb = findp(rb);
		    			g[ra].insert(rb); gg[rb].insert(ra);
		    		}
		    	} 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;
}

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