Submission #249565

#	Time	Username	Problem	Language	Result	Execution time	Memory
249565		srvlt	Special graph (IZhO13_specialg)	C++14	100 / 100	95 ms	39152 KiB

specialg

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int n0 = 2e5 + 123, k0 = 18, inf = 1e9;
int n, m, a[n0], t[n0], used[n0], par[n0], up[k0][n0], mn[k0][n0];
int in[n0], out[n0], T, h[n0], lg[n0], head[n0], timer;
array <int, 3> q[n0];
vector <int> g[n0];

int arr[n0], k, sp[k0][n0], c[n0], cnt, sz[n0], pos[n0];
vector <int> vec;

void dfs(int v) {
	used[v] = 1;
	for (int to : g[v]) {
		if (used[to] == 1) {
			int u = v;
			vec.clear();
			while (u != to) vec.pb(u), u = par[u];
			vec.pb(to);
			cnt++;
			for (int i : vec) {
				c[i] = cnt, sz[cnt]++;
				arr[++k] = t[i];
				pos[i] = k;
			}
			for (int i : vec) arr[++k] = t[i];
		}	else {
			par[to] = v;
			if (used[to] == 0)
				dfs(to);
		}
	}
	used[v] = 2;
}

void go(int v, int p) {
	if (c[v]) return;
	if (p == v) head[v] = v;
	used[v] = 1;
	up[0][v] = p;
	mn[0][v] = t[v];
	for (int i = 1; i < k0; i++) {
		up[i][v] = up[i - 1][up[i - 1][v]];
		mn[i][v] = min(mn[i - 1][v], mn[i - 1][up[i - 1][v]]);
	}
	in[v] = ++T;
	for (int to : g[v]) {
		if (c[to] || to == p) continue;
		h[to] = h[v] + 1;
		head[to] = head[v];
		go(to, v);
	}
	out[v] = T;
}

bool upper(int v, int u) {
	return in[v] <= in[u] && out[u] <= out[v];
}

int getmin(int v, int u) {
	if (v == u) return inf;
	assert(upper(u, v));
	int res = inf;
	for (int i = k0 - 1; i >= 0; i--) {
		if (!upper(up[i][v], u)) {
			res = min(res, mn[i][v]);
			v = up[i][v];
		}
	}
	return min(res, mn[0][v]);
}

int get(int l, int r) {
	int len = lg[r - l + 1];
	return min(sp[len][l], sp[len][r - (1 << len) + 1]);
}

int cycle_dist(int v, int u) {
	assert(c[v] && c[u]);
	if (v == u) return 0;
	if (c[v] != c[u]) return -1;
	if (pos[v] < pos[u]) {
		if (get(pos[v], pos[u] - 1) < timer) return -1;
		return pos[u] - pos[v];
	}
	if (pos[v] < pos[u] + sz[c[u]]) {
		if (get(pos[v], pos[u] + sz[c[u]] - 1) < timer) return -1;
		return pos[u] + sz[c[u]] - pos[v];
	}
	assert(false);
}

int dist(int v, int u) {
	if (c[v] && c[u]) return cycle_dist(v, u);
	if (!c[v] && c[u]) {
		int res = h[v] - h[head[v]] + 1;
		if (getmin(v, head[v]) < timer) return -1;
		if (t[head[v]] < timer) return -1;
		v = par[head[v]];
		if (!c[v]) return -1;
		int d = cycle_dist(v, u);
		if (d == -1) return -1;
		return res + d;
	}
	if (!c[v] && !c[u]) {
		if (!upper(u, v)) return -1;
		if (getmin(v, u) < timer) return -1;
		return h[v] - h[u];
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> q[i][0] >> q[i][1];
		if (q[i][0] == 2) cin >> q[i][2];
		else t[q[i][1]] = i;
	}
	for (int i = 1; i <= n; i++) {
		if (t[i] == 0) t[i] = inf;
		g[a[i]].pb(i);
	}
	for (int i = 1; i <= n; i++)
		if (!used[i]) dfs(i);
	for (int i = 1; i <= k; i++)
		sp[0][i] = arr[i];
	for (int i = 1; i < k0; i++)
		for (int j = 1; j + (1 << i) - 1 <= k; j++)
			sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
	for (int i = 2; i <= k; i++)
		lg[i] = lg[i / 2] + 1;
	memset(& used, 0, sizeof(used));
	for (int i = 1; i <= n; i++)
		if (!used[i])
			go(i, i);
	for (int i = 1; i <= m; i++) {
		if (q[i][0] == 2) {
			timer = i;
			cout << dist(q[i][1], q[i][2]) << '\n';
		}
	}
}

• Subtask 1: 100 / 100