Submission #501502

#	Time	Username	Problem	Language	Result	Execution time	Memory
501502		keta_tsimakuridze	Special graph (IZhO13_specialg)	C++14	100 / 100	184 ms	24388 KiB

specialg

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, dep[N], root[N], cycle[N], parent[N], tree[4 * N], p[N], pos[N],n, np, in[N], f[N], st[N], en[N];
int timer, tmin[N], tmout[N];
vector<int> V[N];
vector<int> x;
void dfs(int u,int p, int r) {
	dep[u] = dep[p] + 1;
	root[u] = r; 
	tmin[u] = ++ timer;
	for(int i = 0; i < V[u].size(); i++) {
		if(V[u][i] == p || cycle[V[u][i]]) continue;
		dfs(V[u][i], u, r);
	}
	tmout[u] = timer;
}
int find(int u) {
	return (parent[u] == u ? u : parent[u] = find(parent[u]));
}
void merge(int u,int v) {
	u = find(u), v = find(v);
	if(u == v) return;
	parent[v] = u;
}
void upd(int u,int ind,int l,int r) {
	if(l > ind ||r < ind) return;
	if(l == r) {
		tree[u] = 1;
		return;
	}
	int mid = (l + r) / 2;
	upd(2 * u, ind, l, mid); upd(2 * u + 1, ind, mid + 1, r);
	tree[u] = min(tree[2 * u], tree[2 * u + 1]);
}
int get(int u,int st,int en,int l, int r) {
	if(l > en || r < st) return 1;
	if(st <= l && r <= en) return tree[u];
	int mid = (l + r) / 2;
	return get(2 * u, st, en, l, mid) & get(2 * u + 1, st, en, mid + 1, r);
}
bool check(int u,int v) {
	return (tmin[u] <= tmin[v] && tmin[v] <= tmout[u]);
}
main(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> p[i], in[p[i]]++, V[p[i]].push_back(i);
	queue<int> q;
	for(int i = 1; i <= n; i++) {
		if(!in[i]) q.push(i);
	}
	while(q.size()) {
		int u = q.front(); 
		q.pop();
		f[u] = 1;
		in[p[u]]--;
		if(p[u] && !in[p[u]]) q.push(p[u]);
	}
	int id = 0, idx = 0;
	for(int i = 1; i <= n; i++) {
		if(!f[i]) {
			int u = i;
			id++;
			st[id] = idx + 1;
			while(u && !f[u]) {
				cycle[u] = id;
				pos[u] = ++idx;
				f[u] = 1;
				en[id] = idx;
				u = p[u];
				
			}
		}
		if(cycle[i]) dfs(i, 0, i);
	}
	dfs(0, 0, 0);
	int m;
	memset(f, 0, sizeof(f));
	cin >> m;
	vector<int> ty(m + 5), v(m + 5), u(m + 5);
	for(int i = 1; i <= m; i++) {
		cin >> ty[i];
		if(ty[i] == 1) cin >> v[i], f[v[i]] = 1;
		else cin >> u[i] >> v[i];
	}
	for(int i = 1; i <= n; i++) parent[i] = i;
	for(int i = 1; i <= n; i++) {
		if(!f[i] && p[i]) merge(i, p[i]), upd(1, pos[i], 1, n);
	}
	for(int i = m; i >= 1; i--) {
		if(ty[i] == 1) {
			if(p[v[i]]) merge(v[i], p[v[i]]), upd(1, pos[v[i]], 1, n);
			continue;
		} 
		if(check(v[i], u[i]) && find(v[i]) == find(u[i])) x.push_back(dep[u[i]] - dep[v[i]]);
		else
		if(v[i] != root[v[i]]) x.push_back(-1);
		else if(cycle[root[u[i]]] != cycle[root[v[i]]]) x.push_back(-1);
		else if(find(u[i]) != find(root[u[i]]) || find(v[i]) != find(root[v[i]]))x.push_back(-1);
		else {
			int ans = dep[u[i]] + dep[v[i]] - 2;
			u[i] = root[u[i]]; v[i] = root[v[i]]; 
			int c = cycle[u[i]];
			u[i] = pos[u[i]], v[i] = pos[v[i]];
			if(u[i] <= v[i]) {
				if(get(1, u[i], v[i] - 1, 1, n)) x.push_back(v[i] - u[i] + ans);//cout << v[i] - u[i] + ans << endl;
				else x.push_back(-1);
			}
			else {
				if(get(1, u[i], en[c], 1, n) && get(1, st[c], v[i] - 1, 1, n)) {
					x.push_back( en[c] - u[i] + 1 + v[i] - st[c] + ans );
				}
				else x.push_back(-1);
			}
		}
	}
	for(int i = (int)x.size() - 1; i >= 0; i--) cout << x[i] <<"\n";
	
}

Compilation message (stderr)

specialg.cpp: In function 'void dfs(long long int, long long int, long long int)':
specialg.cpp:16:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
specialg.cpp: At global scope:
specialg.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main(){
      | ^~~~

• Subtask 1: 100 / 100