Submission #597742

#	Time	Username	Problem	Language	Result	Execution time	Memory
597742		penguinhacker	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	12 ms	21460 KiB

joitter2

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

#define ll long long
#define ar array

#define dbg(x) cerr << "[" << #x << "] = [" << x << "]\n"

template<class T> ostream& operator<< (ostream& out, vector<T> v) {
	out << '[';
	for (int i = 0; i < v.size(); ++i) {
		if (i > 0) {
			out << ", ";
		}
		out << v[i];
	}
	return out << ']';
}

template<class T> ostream& operator<< (ostream& out, set<T> v) {
	return out << vector<T>(v.begin(), v.end());
}

template<class A, size_t sz> ostream& operator<< (ostream& out, ar<A, sz> a) {
	out << '[';
	for (int i = 0; i < sz; ++i) {
		if (i > 0) out << ", ";
		out << a[i];
	}
	return out << ']';
}

template<class A, class B> ostream& operator<< (ostream& out, pair<A, B> p) {
	return out << '[' << p.first << ", " << p.second << ']';
}

template<class A, class B> ostream& operator<< (ostream& out, map<A, B> mp) {
	return out << vector<pair<A, B>>(mp.begin(), mp.end());
}

const int mxN=1e5;
int n, m, p[mxN];
set<int> adj[mxN][2], to[mxN], back[mxN]; // forward and backward edges to other components, from i->component, component->i
vector<int> cmp[mxN];
queue<ar<int, 2>> q;
ll ans;

int find(int i) {
	return i^p[i]?p[i]=find(p[i]):i;
}

ll calc(int i) {
	assert(i==p[i]);
	ll x=cmp[i].size();
	return x*(x-1)+(ll)back[i].size()*x;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<n; ++i) {
		p[i]=i;
		cmp[i]={i};
	}
	while(m--) {
		int u, v;
		cin >> u >> v, --u, --v;
		if (find(u)==find(v))
			continue;
		if (to[u].find(find(v))==to[u].end()) {
			ans+=cmp[find(v)].size();
			to[u].insert(find(v));
			back[find(v)].insert(u);
		}
		u=find(u), v=find(v);
		if (adj[u][0].find(v)==adj[u][0].end()) {
			adj[u][0].insert(v);
			adj[v][1].insert(u);
			if (adj[u][1].find(v)!=adj[u][1].end())
				q.push({u, v});
		}
		for (; q.size(); q.pop()) {
			u=find(q.front()[0]), v=find(q.front()[1]);
			//cout << "trying to merge " << u << " " << v << endl;
			//dbg(to[u]), dbg(to[v]), dbg(back[u]), dbg(back[v]);
			if (u==v)
				continue;
			if (cmp[u].size()<cmp[v].size())
				swap(u, v);
			ans-=calc(u)+calc(v);
			for (int j : {0, 1}) {
				for (int rep=0; rep<2; ++rep) {
					auto it=adj[u][j].find(v);
					assert(it!=adj[u][j].end());
					adj[u][j].erase(it);
					swap(u, v);
				}
			}
			for (int i : cmp[v]) {
				if (to[i].find(u)!=to[i].end()) {
					to[i].erase(u);
					back[u].erase(i);
				}
				cmp[u].push_back(i);
			}
			vector<int>().swap(cmp[v]);
			for (int i : back[v]) {
				auto it=to[i].find(v);
				assert(it!=to[i].end());
				to[i].erase(it);
				if (find(i)!=u) {
					to[i].insert(u);
					back[u].insert(i);
				}
			}
			set<int>().swap(back[v]);
			//back[u].erase(v);
			//cout << adj[v][0].size() << " " << adj[v][1].size() << " " << adj[0][0].size() << endl;
			for (int j : {0, 1}) {
				for (int i : adj[v][j]) {
					//cout << j << " " << v << " " << i << endl;
					adj[u][j].insert(i);
					auto it=adj[i][j^1].find(v);
					assert(it!=adj[i][j^1].end());
					adj[i][j^1].erase(it);
					adj[i][j^1].insert(u);
					if (adj[u][j^1].find(i)!=adj[u][j^1].end())
						q.push({u, i});
				}
				set<int>().swap(adj[v][j]);
			}
			//dbg(to[u]), dbg(to[v]), dbg(back[u]), dbg(back[v]);
			ans+=calc(u);
			p[v]=u;
		}
		cout << ans << "\n";
	}
	return 0;
}

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