oj.uz

Submission #543232

# Submission time Handle Problem Language Result Execution time Memory
543232 2022-03-29T22:10:32 Z sidon Special graph (IZhO13_specialg) C++17
100 / 100
 123 ms 32420 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3028 KB Output is correct
2 Correct 3 ms 3156 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 5 ms 3136 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 10 ms 3412 KB Output is correct
7 Correct 10 ms 3540 KB Output is correct
8 Correct 11 ms 3580 KB Output is correct
9 Correct 10 ms 3552 KB Output is correct
10 Correct 11 ms 3544 KB Output is correct
11 Correct 107 ms 32360 KB Output is correct
12 Correct 96 ms 19644 KB Output is correct
13 Correct 106 ms 24548 KB Output is correct
14 Correct 89 ms 17828 KB Output is correct
15 Correct 97 ms 20484 KB Output is correct
16 Correct 89 ms 19912 KB Output is correct
17 Correct 114 ms 29780 KB Output is correct
18 Correct 119 ms 29828 KB Output is correct
19 Correct 123 ms 29960 KB Output is correct
20 Correct 107 ms 32420 KB Output is correct