Submission #47553

#	Time	Username	Problem	Language	Result	Execution time	Memory
47553		minkank	Special graph (IZhO13_specialg)	C++17	0 / 100	7 ms	5368 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], bit[N];

int get(int t, int pos) {
	//cout << t << ' ' << bit[t].size() << endl;
	int res = 0;
	for(pos; pos > 0; pos -= pos & -pos)
		res += bit[t][pos];
	return res;
}

void upd(int t, int pos) {
	for(pos; pos <= sz[t]; pos += pos & -pos)
		bit[t][pos]++;	
}

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);
		//cout << root_cir[6] << endl;
		bit[cnt].assign(sz[cnt] + 5, 0);
	}
	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]);
		if(i == root[i]) upd(root_cir[i], pos[i]);
	}
	for(int i = m; i >= 1; --i) {
		if(qu[i].type == 1) {
			join(qu[i].x, qu[i].y);
			if(qu[i].x == root[qu[i].x]) {
				upd(root_cir[qu[i].x], pos[qu[i].x]);
			}
		}
		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];
						int cir = root_cir[s];
						if(s <= t) {
							if(get(cir, pos[t] - 1) - get(cir, pos[s] - 1) != pos[t] - pos[s]) 
								ans[i] = -1;
							else ans[i] += pos[t] - pos[s];
						}
						else {
							if(get(cir, sz[root_cir[s]]) - get(cir, pos[s] - 1) + get(cir, pos[t] - 1) != (sz[root_cir[s]]) - pos[s] + pos[t])
								ans[i] = -1;
							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';
}

Compilation message (stderr)

specialg.cpp: In function 'int get(int, int)':
specialg.cpp:17:9: warning: statement has no effect [-Wunused-value]
  for(pos; pos > 0; pos -= pos & -pos)
         ^
specialg.cpp: In function 'void upd(int, int)':
specialg.cpp:23:9: warning: statement has no effect [-Wunused-value]
  for(pos; pos <= sz[t]; pos += pos & -pos)
         ^

• Subtask 1: 0 / 100