Submission #1171333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171333		pinbu	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	0 / 100	10 ms	19008 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], cc[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 (s1[r1].find({u, v}) != s1[r1].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);
		    		// if (u == 2 && v == 1) cerr << "*" << r2 << ' ' << ans << ' ' << sout[r1].size() << '\n';
		    		for (auto [a, b]: s1[r2]) {
		    			if (findp(b) ^ r1) {
		    				// cerr << "?\n";
		    				sout[r1].insert(b);
		    				s1[r1].insert({a, b});
		    				qu.push({b, a});
		    			}
		    		}
		    		for (auto [a, b]: s2[r2]) {
		    			if (findp(b) ^ r1) {
		    				s2[r1].insert({a, b});
		    				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];
					// cerr << sz[r1] << ' ' << sout[r1].size() << '\n';
		    		par[r2] = r1;
		    	} else if (sout[r2].find(u) == sout[r2].end()) {
		    		sout[r2].insert(u);
		    		s1[r2].insert({v, u});
		    		s2[r1].insert({u, v});
		    		ans += sz[r2];
		    	}
			}
		}
    	cout << ans << '\n';
    }
    
    return 0;
}

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