Submission #1116151

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1116151	2024-11-21T09:37:47 Z	Tsagana	Special graph (IZhO13_specialg)	C++14	0 / 100	17 ms	65536 KB

specialg

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

#define sp << ' ' <<
#define nl << '\n'

using namespace std;

vector<int> dq[200001][21];
int dp[200005][21];
bool id[200005];
int lvl[200005];
int n, q, m;

void dfs(int s) {
	if (id[s]) return;
	
	id[s] = 1;
	dfs(dp[s][0]);
	lvl[s] = lvl[dp[s][0]] + 1;
}

void prep() {
	for (int j = 1; j <= 20; j++) 
	for (int i = 1; i <= n;  i++) {
		dp[i][j] = dp[dp[i][j-1]][j-1];
		dq[dp[dp[i][j-1]][j-1]][j].pb(i);
	}

	// for (int i = 1; i <= n;  i++)
	// for (int j = 0; j <= 20; j++) {
	// 	cout << i sp j nl << ": ";
	// 	for (auto l: dq[i][j]) cout << l << ' ';
	// 	cout << '\n';
	// }
		
	for  (int i = 1; i <= m; i++) if (!id[i]) dfs(i);
}

int jump(int a, int k) {
	if (k <= 0) return a;

	for (int i = 20; i >= 0; i--) {
		if (k < (1 << i)) continue ;
		k -= (1 << i);
		a = dp[a][i];
	}
	return a;
}

bool check(int x, int y, int k, int a) {
	for (auto b: dq[x][0]) if (dp[b][k] != a) return 0;

	// better 
	// if (dp[dq[x][0][0]][k] != a) return 0;

	return 1;
}

void cut(int x) {
	int y = dp[x][0];

	for (int i = 0; i <= 20; i++) {
		for (auto l: dq[y][i]) {
			if (!check(l, y, i, x)) continue ;
			
			for (int j = i; j <= 20; j++) {
				dp[l][j] = -1;
			}
		}
		dp[x][i] = -1;
	}
}

int find(int x, int y) {
	int a = jump(x, lvl[x]);

	if (jump(x, lvl[x] - lvl[y]) == y) return lvl[x] - lvl[y];
	if (jump(a, lvl[a] - lvl[y]) == y) return lvl[x] + lvl[a] - lvl[y];
	return -1;
}

void solve(){
	cin >> n;

	int in[100001];

	for (int i = 1; i <= n; i++) {
		cin >> dp[i][0];
		in[dp[i][0]] = 1;
		dq[dp[i][0]][0].pb(i);
	}

	m = n;
	for (int i = 1; i <= m; i++) if (!in[i]) {
		dp[++n][0] = i;
		dq[i][0].pb(n);
	}

	prep();

	cin >> q;
	while (q--) {
		int t; cin >> t;

		if (t == 1) {int x; cin >> x; cut(x);}
		else {
			int x, y; cin >> x >> y;
			cout << find(x, y) nl;
		}
	}
}	
signed main() {IOS solve(); return 0;}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	17 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-