Submission #472386

#	Time	Username	Problem	Language	Result	Execution time	Memory
472386		sidon	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1699 ms	102580 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];
 
			for(int w : g[v]) {
				g[u].insert(w);
				w = find(w);
				if(g[w].find(u) != end(g[w])) Q.push({u, w});
				out[u][w] += out[v][w];
				out[v][w] = 0;
			}
 
 			for(int w : h[v]) {
				if(find(w) != u && find(w) != v) {
					if(g[u].find(find(w)) != end(g[u])) Q.push({u, w});
					if(h[u].find(w) != end(h[u])) {
						edge_count -= S[u];
						--in[u];
					} else {
						g[find(w)].insert(u);
						++out[find(w)][u];
					}
				}

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

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