답안 #249565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
249565 2020-07-15T09:49:54 Z srvlt 특수한 그래프 (IZhO13_specialg) C++14
100 / 100
95 ms 39152 KB
#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';
		}
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6400 KB Output is correct
2 Correct 7 ms 6528 KB Output is correct
3 Correct 6 ms 6528 KB Output is correct
4 Correct 9 ms 6528 KB Output is correct
5 Correct 8 ms 6528 KB Output is correct
6 Correct 11 ms 6912 KB Output is correct
7 Correct 11 ms 7040 KB Output is correct
8 Correct 11 ms 7044 KB Output is correct
9 Correct 11 ms 7040 KB Output is correct
10 Correct 11 ms 7040 KB Output is correct
11 Correct 82 ms 39152 KB Output is correct
12 Correct 77 ms 24568 KB Output is correct
13 Correct 91 ms 30032 KB Output is correct
14 Correct 71 ms 22392 KB Output is correct
15 Correct 78 ms 25464 KB Output is correct
16 Correct 80 ms 24956 KB Output is correct
17 Correct 93 ms 35956 KB Output is correct
18 Correct 93 ms 35956 KB Output is correct
19 Correct 95 ms 35956 KB Output is correct
20 Correct 82 ms 39152 KB Output is correct