제출 #404387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
404387		ntabc05101	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	100 / 100	1232 ms	69000 KiB

joitter2

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

#define f first
#define s second

using ll = long long;

const int mxN = 100000;

int par[mxN + 5];
ll sz[mxN + 5];
ll result = 0;

set<int> ccs[mxN + 5], ou[mxN + 5], in[mxN + 5];
queue< pair<int, int> > to_merge;

void weak_connection(int x, int y) {
	ou[x].insert(y); in[y].insert(x);
	if (ou[y].count(x)) to_merge.emplace(x, y);
}

int tot_sz(int x) {
	return ccs[x].size() + in[x].size() + ou[x].size();
}

int find(int x) {
	return (x == par[x] ? x: par[x] = find(par[x]));
}

void unite_set(int x, int y) {
	if (x == y) return ;
	if (tot_sz(x) < tot_sz(y)) swap(x, y);
	
	result += sz[y] * ccs[x].size() + sz[x] * ccs[y].size();
	
	par[y] = x; sz[x] += sz[y];
	
	for (int u: ccs[y]) {
		if (ccs[x].count(u)) result -= sz[x];
		else ccs[x].emplace(u);
	}
	
	ou[x].erase(y); in[x].erase(y);
	ou[y].erase(x); in[y].erase(x);
	for (int u: ou[y]) {
		in[u].erase(y);
		weak_connection(x, u);
	}
	for (int u: in[y]) {
		ou[u].erase(y);
		weak_connection(u, x);
	}
}


int main() {
        cin.tie(0)->sync_with_stdio(0);
        
        int n, m; cin >> n >> m;
        for (int i = 1; i <= n; i++) {
        	par[i] = i;
        	sz[i] = 1;
        	ccs[i].insert(i);
        }
        
        int x, y;
        while (m--) {
        	cin >> x >> y;
        	
        	y = find(y);
        	if (find(x) != y && !ccs[y].count(x)) {
	       		ccs[y].emplace(x);
        		result += sz[y];
        		
        		x = find(x);
        		weak_connection(x, y);
        		while (!to_merge.empty()) {
        			tie(x, y) = to_merge.front();
        			to_merge.pop();
        			
        			unite_set(find(x), find(y));
        		}
        	}
        	
        	cout << result << "\n";
        }

        return 0;
}

/*
4 6
1 2
2 3
3 2
1 3
3 4
4 3
*/

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