Submission #47540

#	Time	Username	Problem	Language	Result	Execution time	Memory
47540		minkank	Special graph (IZhO13_specialg)	C++14	0 / 100	5 ms	2936 KiB

specialg

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

const int N = 1e5 + 5;

struct {
	int type, x, y;
} qu[N];

int n, m, p[N], deg[N], h[N], to[N], root[N], pos[N], root_cir[N], sz[N], check[N], ans[N];
int par[N][20];
vector<int> a[N];

void dfs(int u, int p) {
	par[u][0] = p;
	for(int v: a[u]) if(v != p) {
		if(deg[v]) continue;
		h[v] = h[u] + 1;
		root[v] = root[u];
		dfs(v, u);
	}
}

int cnt;

int lca(int u, int v) {
	for(int i = 17; i >= 0; --i) if(h[par[u][i]] >= h[v]) u = par[u][i];
	for(int i = 17; i >= 0; --i) if(h[par[v][i]] >= h[u]) v = par[v][i];
	for(int i = 17; i >= 0; --i) if(par[v][i] != par[u][i])
		u = par[u][i], v = par[v][i];
	if(u != v) u = par[u][0];
	return u;
}

void find_cir(int u, int root) {
	int v = p[u];
	check[u] = true;
	pos[u] = sz[cnt]++;
	root_cir[u] = cnt;
	if(v == root) return;
	find_cir(v, root);
}

int find(int u) {
	if(to[u] == u) return u;
	return to[u] = find(to[u]);
}

void join(int u, int v) {
	u = find(u);
	v = find(v);
	if(u != v) to[u] = v;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> p[i];
		a[p[i]].push_back(i);
		deg[p[i]]++;
	}
	queue<int> Q;
	for(int i = 1; i <= n; ++i) if(!deg[i]) Q.push(i);
	while(Q.size()) {
		int u = Q.front(); Q.pop();
		if(p[u] == 0) continue;
		deg[p[u]]--; if(!deg[p[u]]) Q.push(p[u]);
	}
	for(int i = 1; i <= n; ++i) if(deg[i] || p[i] == 0) {
		root[i] = i;
		dfs(i, i);
	}
	for(int i = 1; i <= n; ++i) if(deg[i] && !check[i]) {
		cnt++;
		find_cir(i, i);
	}
	for(int i = 1; i <= 17; ++i) for(int j = 1; j <= n; ++j)
		par[j][i] = par[par[j][i - 1]][i - 1];
	cin >> m;
	for(int i = 1; i <= m; ++i) {
		cin >> qu[i].type;
		if(qu[i].type == 1) {
			cin >> qu[i].x; qu[i].y = p[qu[i].x];
			p[qu[i].x] = 0;
		}
		else cin >> qu[i].x >> qu[i].y;
	}
	for(int i = 1; i <= n; ++i) to[i] = i;
	for(int i = 1; i <= n; ++i) if(p[i]) join(i, p[i]);
	for(int i = m; i >= 1; --i) {
		if(qu[i].type == 1) {
			join(qu[i].x, qu[i].y);
		}
		else {
			int s = qu[i].x, t = qu[i].y;
			if(find(s) != find(t)) ans[i] = -1;
			else {
				if(root[s] == root[t]) {
					int L = lca(s, t);
					if(s != L && t != L) ans[i] = -1;
					else ans[i] = abs(h[s] - h[t]);
				}
				else {
					if(root[s] != s && root[t] != t)
						ans[i] = -1;
					else {
						ans[i] += h[s] + h[t];
						s = root[s]; t = root[t];
						if(s <= t) ans[i] += pos[t] - pos[s];
						else ans[i] += sz[root_cir[s]] - pos[s] + pos[t];
					}
				}
			}
		}
	}
	for(int i = 1; i <= m; ++i) if(qu[i].type == 2)
		cout << ans[i] << '\n';
}

• Subtask 1: 0 / 100