Submission #84464

#	Time	Username	Problem	Language	Result	Execution time	Memory
84464		ekrem	Special graph (IZhO13_specialg)	C++98	0 / 100	24 ms	24568 KiB

specialg

//Boyle sorunun amk


#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;
typedef long long ll;
ll n, q, m, cem, a[N], b[N], c[N], git[25][N], t[N], ag[N];
ll x[N], yer[N], u[N], der[N], amk[N], ata[N], fen[N];
vector < ll > g[N], ans;

ll atabul(ll x){
	if(ata[x] != x)
		ata[x] = atabul(ata[x]);
	return ata[x];}
void up(ll x, ll y){
	for(; x <= m; x += x&-x)
		fen[x] += y;}
ll qu(ll x){
	if(x == 0)
		return 0;
	ll top = 0;
	for(; x > 0; x -= x&-x)
		top += fen[x];
	return top;}
void hazirla();
void dfs(ll node){
	u[node] = 1;
	if(u[git[0][node]]){
		cem = node;
		return;
	}
	dfs(git[0][node]);}
void dfs2(ll node, ll dr, ll at){
	ag[node] = at;
	der[node] = dr;
	for(ll i = 0; i < g[node].size(); i++)
		dfs2(g[node][i], dr + 1, at);}
ll lca(ll x, ll y){
	ll ans = 0;
	for(ll i = 21; i >= 0; i--){
		// cout << x << " " << y << endl;
		if(der[y] <= der[git[i][x]] and (1<<i) <= der[x]){
			ans += 1<<i;
			x = git[i][x];
		}
	}
	if(x == y)
		return ans;
	return -1;}
ll yolver(ll x, ll y){
	ll i = yer[x];
	ll j = yer[y];
	if(i <= j){
		ll ara = qu(j - 1) - qu(i - 1);
		if(ara)
			return -1;
		return j - i;
	}
	ll ara = qu(m) - qu(i - 1) + qu(j - 1);
	if(ara)
		return -1;
	return m - i + j;}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%lld",&n);
	for(ll i = 1; i <= n; i++){
		scanf("%lld",&git[0][i]);
		amk[i] = git[0][i];
	}

	hazirla();

	for(ll i = 1; i <= n; i++){
		if(yer[i])
			continue;
		g[git[0][i]].pb(i);
	}

	for(ll i = 1; i <= m; i++)
		dfs2(x[i], 0, x[i]);


	scanf("%lld",&q);
	for(ll i = 1; i <= q; i++){
		scanf("%lld %lld",c + i, a + i);
		if(c[i] == 2)
			scanf("%lld", b + i);
		else{
			if(yer[a[i]] == 0)
				amk[a[i]] = 0;
			else
				up(yer[a[i]], 1);
			c[i] = git[0][i];
		}
	}
	for(ll i = 1; i <= n; i++)
		if(amk[i]){
			ll xx = atabul(i);
			ll yy = atabul(amk[i]);
			if(xx != yy)
				ata[xx] = yy;
		}
	// for(ll i = 1; i <= n; i++)cout << ag[i] << " ";cout << endl;

	for(ll i = q; i >= 1; i--){
		if(c[i] == 2){
			ll xx = atabul(a[i]);
			ll yy = atabul(b[i]);
			if(xx != yy){
				ans.pb(-1);
				continue;
			}
			// cout << a[i] << " " << b[i] << "AMKXX" << endl;
			ll l;;
			if(ag[b[i]] != ag[a[i]])
				l = ag[a[i]];
			else
				l = b[i];
			ll yol = lca(a[i], l);
			// cout << a[i] << " " << l << " e yol = " << yol << endl;
			if(yol == -1){
				ans.pb(-1);
				continue;
			}
			if(l != b[i]){
				ll orz = yolver(l, b[i]);
				// cout << l << " " << b[i] << " = " << orz << endl;
				if(orz == -1)
					ans.pb(-1);
				else
					ans.pb(yol + orz);
			} else
				ans.pb(yol);
		}
		else{
			if(yer[a[i]] == 0){
				ll xx = atabul(a[i]);
				ll yy = atabul(git[0][a[i]]);
				// cout << "YOl eklendi " << a[i] << " -> "<<git[0][a[i]] << endl;
				if(xx != yy)
					ata[xx] = yy;
			}
			else{
				// cout << yer[a[i]] << " bir eksiltildi" << endl;
				up(yer[a[i]], -1);
			}
		}
	}
	reverse(ans.begin(), ans.end());
	for(ll i = 0; i < ans.size(); i++)
		printf("%lld\n", ans[i]);
	return 0;
}



void hazirla(){
	for(ll i = 1; i <= 21; i++)
		for(ll j = 1; j <= n; j++)
			git[i][j] = git[i - 1][git[i - 1][j]];
	dfs(1);
	ll node = cem;
	while(1){
		x[++m] = node;
		yer[node] = m;
		node = git[0][node];
		if(node == cem)
			break;
	}
	for(ll i = 1; i <= n; i++)
		ata[i] = i;
}

Compilation message (stderr)

specialg.cpp: In function 'void dfs2(ll, ll, ll)':
specialg.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i = 0; i < g[node].size(); i++)
                ~~^~~~~~~~~~~~~~~~
specialg.cpp: In function 'int main()':
specialg.cpp:157:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i = 0; i < ans.size(); i++)
                ~~^~~~~~~~~~~~
specialg.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
specialg.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&git[0][i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~
specialg.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&q);
  ~~~~~^~~~~~~~~~~
specialg.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",c + i, a + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
specialg.cpp:94:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", b + i);
    ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 100