Submission #245579

#	Time	Username	Problem	Language	Result	Execution time	Memory
245579		kostia244	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	4081 ms	116192 KiB

joitter2

#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,ssse3,popcnt")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
struct edge {
	int f, t, ri, r = 0;
	edge(int f, int t, int ri) : f(f), t(t), ri(ri) {}
};
struct dsu {
	ll ans = 0, T = 69;
	vector<int> r, p, w, tbd;
	vector<vector<int>> g, gr;
	map<pair<int, int>, int> ctc, rtc;
	vector<edge> ve;
	queue<int> mrg;
	int have(int i, int j) { return ctc[{i, j}]; }
	void add(int i, int j) { ctc[{i, j}]++; }
	void rem(int i, int j) { ctc[{i, j}]--; }
	void iadd(int i, int j) { rtc[{i, j}]++; }
	void irem(int i, int j) { rtc[{i, j}]--; }
	int ihave(int i, int j) { return rtc[{i, j}]; }
	dsu(int n) : r(n+1, 1), p(n+1), g(n+1), gr(n+1), w(n+1), tbd(n+1) {iota(all(p), 0);}
	int par(int i) {
		return p[i] == i ? i : p[i] = par(p[i]);
	}
	int unite(int i, int j) {
		//cout << i << " " << j << endl;
		if(r[i] < r[j]) swap(i, j);
		//cout << i << " " << j << " | " << r[i] << " " << r[j] << " " << w[i] << " " << w[j] << endl;
		ans -= r[i]*1ll*(r[i]+w[i]-1) + r[j]*1ll*(r[j]+w[j]-1);
		//cout << ans << endl;
		w[i] += w[j];
		r[i] += r[j];
		p[j] = i;
		for(int U = 0; U < 2; U++)
		for(auto &x : (U?gr:g)[j]) {
			auto &e = ve[x];
			if(e.r) continue;
			rem(e.f, e.t);
			irem(e.ri, e.t);
			if(U) e.t = i;
			else e.f = i;
			int p = U?e.f:e.t;assert(p == (e.f^e.t^i));
			if(tbd[p] != T && have(e.t, e.f)) {
				mrg.push(p);
				tbd[p] = T;
			}
			if(ihave(e.ri, e.t) || e.f == e.t) {e.r = 1, w[i]--; continue;}//fucking useless
			(U?gr:g)[i].push_back(x);
			add(e.f, e.t);
			iadd(e.ri, e.t);
		}
		//cout << r[i] << " " << w[i] << endl;
		ans += r[i]*1ll*(r[i]+w[i]-1);
		return i;
	}
	void adde(int i, int j) {
		++T;
		int ri = i;
		//cout << i << " " << j << " ";
		i = par(i), j = par(j);
		//cout << i << " " << j << "\n";
		if(i == j) return;
		if(ihave(ri, j)) return;
		w[j]++, ans += r[j];
		ve.emplace_back(i, j, ri);
		g[i].push_back(ve.size()-1);
		gr[j].push_back(ve.size()-1);
		add(i, j);
		iadd(ri, j);
		if(have(j, i)) {
			int cur = i;
			tbd[i] = tbd[j] = T;
			mrg.push(j);
			while(!mrg.empty()) {
				cur = unite(cur, mrg.front());
				mrg.pop();
			}
		}
	}
};
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	dsu d(n);
	for(int f, t, i = 0; i < m; i++) {
		cin >> f >> t;
		d.adde(f, t);
		cout << d.ans << endl;
	}
}

Compilation message (stderr)

joitter2.cpp: In constructor 'dsu::dsu(int)':
joitter2.cpp:14:25: warning: 'dsu::gr' will be initialized after [-Wreorder]
  vector<vector<int>> g, gr;
                         ^~
joitter2.cpp:13:20: warning:   'std::vector<int> dsu::w' [-Wreorder]
  vector<int> r, p, w, tbd;
                    ^
joitter2.cpp:24:2: warning:   when initialized here [-Wreorder]
  dsu(int n) : r(n+1, 1), p(n+1), g(n+1), gr(n+1), w(n+1), tbd(n+1) {iota(all(p), 0);}
  ^~~

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