Submission #1169731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169731		pinbu	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	0 / 100	4 ms	9792 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> adj[N], out[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) + out[r1].size() * sz[r1];
	    		ans -= sz[r2] * (sz[r2] - 1) + out[r2].size() * sz[r2];
	    		out[r1].erase(v);
    			if (out[r1].size() < out[r2].size()) swap(r1, r2);
	    		par[r2] = r1;
	    		sz[r1] += sz[r2];
	    		for (int o: out[r2]) out[r1].insert(o);
	    		// cerr << u << ' ' << v << ' ' << sz[r1] << ' ' << ans << ' ' << out[r1].size() << '\n';
	    		ans += sz[r1] * (sz[r1] - 1) + out[r1].size() * sz[r1];
    		}
    	} else {
    		int r1 = findp(u), r2 = findp(v);
    		if (r1 ^ r2) {
    			if (out[r2].find(u) == out[r2].end()) {
    				out[r2].insert(u);
    				ans += sz[r2];
    			}
    		}
    	}
    	cout << ans << '\n';
    }
    
    return 0;
}

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