제출 #472323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472323		sidon	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	8 ms	15200 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define sz(Z) ll(size(Z))
 
const int MAX_N = 100'001;
 
int N, M;
 
int P[MAX_N];
ll in[MAX_N], S[MAX_N], edge_count;
 
set<int> g[MAX_N], h[MAX_N];
unordered_map<int, int> out[MAX_N];

queue<array<int, 2>> Q;

int find(int u){
	return P[u] == u ? u : P[u] = find(P[u]);
}
 
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
 
	cin >> N >> M;
 
	for(int u = 1; u <= N; ++u){
		P[u] = u;
		S[u] = 1;
	}
 
	while(M--){
		int A, B;
		cin >> A >> B;
 
		int u = find(A), v = find(B);
 
		if(u != v && h[v].find(A) == end(h[v])){
			if(g[v].find(u) != end(g[v]))
				Q.push({u, v});
	 
			edge_count += S[v];
	 
			h[v].insert(A);
			g[u].insert(v);
			++out[u][v];
			++in[v];
		}
 
		while(!empty(Q)) {
			u = find(Q.front()[0]), v = find(Q.front()[1]);
			Q.pop();
			if(u == v) continue;
 
			if(sz(g[u]) + sz(h[u]) < sz(g[v]) + sz(h[v]))
				swap(u, v);
 
			edge_count += (S[u] - out[u][v]) * S[v];
			edge_count += (S[v] - out[v][u]) * S[u];

			in[u] -= out[v][u];
			in[v] -= out[u][v];
 
			edge_count += in[u] * S[v] + in[v] * S[u];
 
			for(int w : g[v]) {
				if(h[u].find(find(w)) != end(h[u])) Q.push({u, w});
				out[u][find(w)] += out[v][find(w)];
				out[v][find(w)] = 0;
			}
 
			for(auto i = begin(h[v]); i != end(h[v]); ) {
				if(g[u].find(find(*i)) != end(g[u])) Q.push({u, *i});
 
				if(find(*i) == u) {
					i = h[v].erase(i);
				} else {
					if(h[u].find(*i) != end(h[u]))
						edge_count -= S[u] + S[v];
					else {
						g[find(*i)].insert(u);
						++out[find(*i)][u];
					}
					++i;
				}
			}

			P[v] = u, S[u] += S[v];

			in[u] += in[v];
 
			g[u].merge(g[v]);
			h[u].merge(h[v]);
		}
 
		cout << edge_count << '\n';
	}
}

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