Submission #543232

#	Time	Username	Problem	Language	Result	Execution time	Memory
543232		sidon	Special graph (IZhO13_specialg)	C++17	100 / 100	123 ms	32420 KiB

specialg

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

const int Z = 1e5, B = 17, INF = 1<<30;

int N, M, to[Z], till[Z];
vector<pair<int, int>> g[Z];
array<int, 3> q[Z+1];

int r, p[Z][B], s[Z][B], d[Z], id[Z], sp[Z], vis[Z];

void dfs(int u) {
	vis[u] = 1;
	id[u] = r;
	for(int i = 0; i + 1 < B; ++i) {
		p[u][i+1] = p[p[u][i]][i];
		s[u][i+1] = min(s[u][i], s[p[u][i]][i]);
	}

	for(const auto &[v, w] : g[u]) {
		if(v != r) {
			p[v][0] = u;
			s[v][0] = w;
			d[v] = d[u] + 1;
			dfs(v);
		} else sp[r] = u;
	}
}

int calc(int u, int v, int t) {
	if(d[u] < d[v]) return INF;
	int res = d[u] - d[v];

	for(int i = B; i--; ) if((d[u] - d[v]) & (1<<i)) {
		if(s[u][i] < t) return INF;
		u = p[u][i];
	}
	return u == v ? res : INF;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N;
	for(int i = 0; i < N; ++i) {
		cin >> to[i];
		till[i] = Z;
		if(!to[i]--) {
			till[i] = 0;
			to[i] = !i;
		}
	}
	cin >> M;

	for(int i = 1; i <= M; ++i) {
		auto &[t, a, b] = q[i];
		cin >> t >> a; --a;
		if(t < 2) till[a] = i;
		else cin >> b, --b;
	}
	for(int i = 0; i < N; ++i)
		g[to[i]].emplace_back(i, till[i]);

	vector<int> roots;
	for(r = 0; r < N; ++r) if(!vis[r]) {
		int u = r;
		while(!vis[u]) vis[u] = r + 1, u = to[u];
		if(vis[u] == r + 1) roots.push_back(u);
	}

	for(const int &u : roots) {
		r = u;
		dfs(p[r][0] = r);
	}

	for(int i = 1; i <= M; ++i) {
		auto [t, u, v] = q[i];
		if(t > 1) {
			int ans = -1;
			if(id[u] == id[v])  {
				ans = calc(u, v, i);
				bool valid = 1;
				int ans2 = d[u] + 1 + calc(sp[id[u]], v, i);
				for(int j = B; j--; ) if(d[u] & (1<<j)) {
					if(s[u][j] < i) valid = 0;
					u = p[u][j];
				}
				if(valid && till[u] >= i) ans = min(ans, ans2);

				if(ans == INF) ans = -1;
			}
			cout << ans << '\n';
		}
	}
}

• Subtask 1: 100 / 100