제출 #1170327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170327		pinbu	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	0 / 100	6 ms	14400 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;
int d[N];
set<int> adj[N], x[N], y[N];

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);
    int ans = 0;
    while (m--) {
    	int u, v; cin >> u >> v;
    	adj[u].insert(v);
    	if (adj[v].find(u) != adj[v].end()) {
    		int r1 = findp(u), r2 = findp(v);
    		if (r1 ^ r2) {
    			ans -= sz[r1] * (sz[r1] - 1) + (x[r1].size() - d[r1]) * sz[r1];
	    		ans -= sz[r2] * (sz[r2] - 1) + (x[r2].size() - d[r2]) * sz[r2];
	    		if (x[r1].size() + y[r1].size() < x[r2].size() + y[r2].size()) {
	    			swap(r1, r2);
	    		}
	    		for (int nu: y[r2]) {
	    			if (findp(nu) ^ r1) {
	    				y[r1].insert(nu);
	    			} else {
	    				d[r1]++;
	    			}
	    		}
	    		for (int nu: x[r2]) {
	    			if (findp(nu) ^ r1) {
	    				x[r1].insert(nu);
	    			}
	    		}
	    		par[r2] = r1;
	    		sz[r1] += sz[r2];
	    		d[r1] += d[r2];
	    		ans += sz[r1] * (sz[r1] - 1) + (x[r1].size() - d[r1]) * sz[r1];
    		}
    	} else {
    		int r1 = findp(u), r2 = findp(v);
    		if (r1 ^ r2) {
    			if (x[r2].find(u) == x[r2].end()) {
    				x[r2].insert(u);
    				y[r1].insert(v);
    				ans += sz[r2];
    			}
    		}
    	}
    	cout << ans << '\n';
    }
    
    return 0;
}

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