Submission #216054

#	Time	Username	Problem	Language	Result	Execution time	Memory
216054		DrumpfTheGodEmperor	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1383 ms	83668 KiB

joitter2

#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 1e5 + 5;
typedef pair<int, int> ii;
struct DSU {
	//For each component, count the amount of inDeg from DISTINCT vertexes from different components.
	int p[N], sz[N];
	set<int> out[N], in[N];
	set<int> distIn[N], have[N];
	bool inQ[N];
	ll compSum = 0, inSum = 0;
	void init(int n) {
		fw (i, 0, n) {
			p[i] = i, sz[i] = 1;
			out[i].clear(), in[i].clear();
			inQ[i] = 0;
			have[i].insert(i);
		}
	}
	int getp(int u) {
		return u == p[u] ? u : p[u] = getp(p[u]);
	}
	void addEdge(int u, int v) {
		int ogu = u;
		u = getp(u), v = getp(v);
		if (u == v) return;
		
		inSum -= 1ll * distIn[v].size() * sz[v];
		distIn[v].insert(ogu);
		inSum += 1ll * distIn[v].size() * sz[v];
		in[v].insert(u);
		out[u].insert(v);
		
		if (!out[v].count(u)) return;
		
		joint(u, v);
	}
	void joint(int u, int v) {
		//Jointing u and v have the side effect of jointing some more vertexes into it. Keep a queue
		queue<int> q;
		q.push(v);
		inQ[v] = 1;
		int root = u;
		while (!q.empty()) {
			int i = q.front(); q.pop();
			inQ[i] = 0;
			if (sz[root] < sz[i]) swap(root, i);
			p[i] = root;
			
			compSum -= 1ll * sz[root] * (sz[root] - 1);
			compSum -= 1ll * sz[i] * (sz[i] - 1);
			inSum -= 1ll * distIn[i].size() * sz[i];
			inSum -= 1ll * distIn[root].size() * sz[root];
			
			sz[root] += sz[i];
			
			compSum += 1ll * sz[root] * (sz[root] - 1);
			//Delete the 2 edges between i and root
			in[i].erase(root), in[root].erase(i), out[i].erase(root), out[root].erase(i);
			
			fa (j, out[i]) {
				out[root].insert(j);
				in[j].erase(i);
				in[j].insert(root);
				
				if (in[root].count(j)) {
					if (!inQ[j]) {
						inQ[j] = 1;
						q.push(j);
					}
				}
			}
			fa (j, in[i]) {
				in[root].insert(j);
				out[j].erase(i);
				out[j].insert(root);
				
				if (out[root].count(j)) {
					if (!inQ[j]) {
						inQ[j] = 1;
						q.push(j);
					}
				}
			}
			
			fa (j, have[i]) {
				have[root].insert(j);
				if (distIn[root].count(j)) distIn[root].erase(j);
			}
			fa (j, distIn[i]) {
				if (!have[root].count(j)) distIn[root].insert(j);
			}
			inSum += 1ll * distIn[root].size() * sz[root];
		}
	}
} dsu;
int n, q;
vector<int> g[N];
bool used[N];
signed main() {
	#ifdef BLU
	in("blu.inp");
//	out("ans1.out");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	dsu.init(n);
	while (q--) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		g[a].pb(b);
//		cout << "Add edge " << a + 1 << " and " << b + 1 << "\n";
		dsu.addEdge(a, b);
		
//		int finalAns = 0;
//		fw (i, 0, n) {
//			finalAns += dsu.sz[dsu.getp(i)] - 1;
//			fa (j, g[i]) if (dsu.getp(j) != dsu.getp(i)) {
//				if (!used[dsu.getp(j)]) finalAns += dsu.sz[dsu.getp(j)];
//				used[dsu.getp(j)] = 1;
//			}
//			fa (j, g[i]) used[dsu.getp(j)] = 0;
//		}
//		cout << finalAns << "\n";
		cout << dsu.compSum + dsu.inSum << "\n";
	}
	return 0;
}

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