Submission #1114659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114659		dubabuba	Special graph (IZhO13_specialg)	C++14	0 / 100	36 ms	25680 KiB

specialg

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

const int LOG = 20;
const int mxn = 1e5 + 10;

vector<int> adj[mxn];
int st[mxn], cyc[mxn], ord[mxn], root[mxn * 4];
int en[mxn], sus[mxn], lvl[mxn], anc[LOG][mxn];
int TIME = 1, nxt[mxn], n;
bool rem[mxn];

void upt(int id, int tl, int tr, int l, int r, int val) {
	// cout << "upt " << tl << ' ' << tr << ": " << l << ' ' << r << ' ' << val << endl;
	if(tl == l && r == tr) {
		// cout << val << endl;
		root[id] = val;
		return;
	}
	
	if(root[id]) {
		root[id * 2 + 1] = root[id];
		root[id * 2 + 2] = root[id];
		root[id] = 0;
	}

	int tm = (tl + tr) / 2;
	if(r <= tm) upt(id * 2 + 1, tl, tm, l, r, val);
	else if(tm < l) upt(id * 2 + 2, tm + 1, tr, l, r, val);
	else {
		upt(id * 2 + 1, tl, tm, l, tm, val);
		upt(id * 2 + 2, tm + 1, tr, tm + 1, r, val);
	}
}

int query(int id, int tl, int tr, int i) {
	// cout << "query " << tl << ' ' << tr << ": " << i << endl;
	// cout << " > root " << id << " = " << root[id] << endl;
	if(root[id]) return root[id];
	assert(tl < tr);
	int tm = (tl + tr) / 2;
	if(i <= tm) return query(id * 2 + 1, tl, tm, i);
	return query(id * 2 + 2, tm + 1, tr, i);
}

void find_cyc(int u) {
	stack<int> st;

	int cur = u;
	while(cur > 0 && cyc[cur] == 0) {
		st.push(cur);
		cyc[cur] = u;
		cur = nxt[cur];
	}

	if(cur > 0 && cyc[cur] == u) {
		int cnt = 1;
		while(st.top() != cur) {
			cyc[st.top()] = cur;
			ord[st.top()] = cnt++;
			st.pop();
		}
		cyc[st.top()] = cur;
		ord[st.top()] = cnt;
		st.pop();
	}

	while(st.size()) {
		cyc[st.top()] = -1;
		st.pop();
	}
}

void euler_dfs(int u, int p, bool debug = false) {
	st[u] = TIME;
	TIME++;
	sus[u] = 0;

	anc[0][u] = p;
	lvl[u] = lvl[p] + 1;
	for(int J = 1; J < LOG; J++) {
		int A = anc[J - 1][u];
		if(A == 0) break;
		anc[J][u] = anc[J - 1][A];
	}

	if(debug)
		cout << p << " -> " << u << endl;
	for(int v : adj[u]) {
		if(v == p) continue;
		if(rem[v]) continue;
		if(v == nxt[u]) continue;
		euler_dfs(v, u, debug);
	}

	en[u] = TIME;
}

void cycle_dfs(int u, int p, int top) {
	sus[u] = top;

	anc[0][u] = p;
	lvl[u] = lvl[p] + 1;
	for(int J = 1; J < LOG; J++) {
		int A = anc[J - 1][u];
		if(A == 0) break;
		anc[J][u] = anc[J - 1][A];
	}

	for(int v : adj[u]) {
		if(v == p) continue;
		if(rem[v]) continue;
		if(cyc[v]) continue;
		cycle_dfs(v, u, top);
	}
}

int cyc_dis(int u, int v) {
	assert(cyc[u] == cyc[v]);
	int ret = ord[u] - ord[v];
	return ret < 0 ? ret + ord[cyc[u]] : ret;
}

int parent(int u) {
	if(sus[u]) return cyc[sus[u]];
	assert(st[u] > 0);
	int ret = query(0, 1, n, st[u]);
	if(ret == 0) for(;1;);
	return ret;
}

int LCA(int u, int v) {
	if(lvl[u] < lvl[v]) swap(u, v);
	int jump = lvl[u] - lvl[v];
	for(int J = 0; J < LOG; J++)
		if(jump & (1 << J))
			u = anc[J][u];
	if(u == v) return u;

	for(int J = LOG - 1; J >= 0; J--) {
		if(anc[J][u] != anc[J][v]) {
			u = anc[J][u];
			v = anc[J][v];
		}
	}
	return anc[0][u];
}

int find_dis(int u, int v) {
	int pu = parent(u); assert(pu > 0);
	int pv = parent(v); assert(pv > 0);
	if(pu != pv) return -1;
	
	if(cyc[pu] == 0) {
		int A = LCA(u, v);
		if(A != v) return -1;
		return lvl[u] + lvl[v] - 2 * lvl[A];
	}

	if(sus[u] == sus[v]) {
		int A = LCA(u, v);
		if(A != v) return -1;
		return lvl[u] + lvl[v] - 2 * lvl[A];
	}

	if(cyc[v] == 0) return -1;
	assert(v == sus[v]);
	return lvl[u] - lvl[pu] + cyc_dis(sus[u], sus[v]);
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> nxt[i];
		adj[i].push_back(nxt[i]);
		adj[nxt[i]].push_back(i);
	}

	for(int i = 1; i <= n; i++)
		if(cyc[i] == 0)
			find_cyc(i);

	for(int i = 1; i <= n; i++)
		if(cyc[i] == -1)
			cyc[i] = 0;

	// cout << "cycles: ";
	// for(int i = 1; i <= n; i++)
	// 	cout << cyc[i] << ' ';
	// cout << endl;

	// cout << "orders: ";
	// for(int i = 1; i <= n; i++)
	// 	cout << ord[i] << ' ';
	// cout << endl;

	for(int i = 1; i <= n; i++) {
		if(nxt[i] == 0) {
			euler_dfs(i, 0);
			upt(0, 1, n, st[i], en[i] - 1, i);
		}
		else {
			cycle_dfs(i, 0, i);
		}
	}

	// for(int i = 1; i <= n; i++) {
	// 	if(sus[i] == 0)
	// 		cout << i << ": " << st[i] << ' ' << en[i] - 1 << endl;
	// 	else
	// 		cout << i << ": " << cyc[i] << ' ' << sus[i] << endl;
	// }

	// for(int i = 1; i <= n; i++)
	// for(int J = 0; J < LOG; J++) {
	// 	if(anc[J][i] == 0) break;
	// 	cout << "jump " << i << ' ' << (1 << J) << " = " << anc[J][i] << endl;
	// }

	int q, t, u, v;
	cin >> q;

	for(int _ = 0; _ < q; _++) {
		cin >> t >> u;

		if(t == 2) {
			cin >> v;
			// cout << "dis " << u << ' ' << v << " = ";
			cout << find_dis(u, v) << endl;
		}
		else {
			rem[u] = true;

			if(sus[u]) {
				if(cyc[u]) {
					int cur = u;
					do {
						cyc[cur] = 0;
						cur = nxt[cur];
					} while(cur != u);
				}
				// euler_dfs(u, 0, true);
				euler_dfs(u, 0);
			}
			// cout << "done\n";
			// cout << st[u] << ' ' << en[u] << endl;
			upt(0, 1, n, st[u], en[u] - 1, u);
		}
	}
	return 0;
}

• Subtask 1: 0 / 100