oj.uz

Submission #84462

# Submission time Handle Problem Language Result Execution time Memory
84462 2018-11-15T09:03:39 Z ekrem Special graph (IZhO13_specialg) C++
0 / 100
 26 ms 24312 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;

int n, q, m, cem, a[N], b[N], c[N], git[25][N], t[N], ag[N];
int x[N], yer[N], u[N], der[N], amk[N], ata[N], fen[N];
vector < int > g[N], ans;

int atabul(int x){
	if(ata[x] != x)
		ata[x] = atabul(ata[x]);
	return ata[x];}
void up(int x, int y){
	for(; x <= m; x += x&-x)
		fen[x] += y;}
int qu(int x){
	if(x == 0)
		return 0;
	int top = 0;
	for(; x > 0; x -= x&-x)
		top += fen[x];
	return top;}
void hazirla();
void dfs(int node){
	u[node] = 1;
	if(u[git[0][node]]){
		cem = node;
		return;
	}
	dfs(git[0][node]);}
void dfs2(int node, int dr, int at){
	ag[node] = at;
	der[node] = dr;
	for(int i = 0; i < g[node].size(); i++)
		dfs2(g[node][i], dr + 1, at);}
int lca(int x, int y){
	int ans = 0;
	for(int 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;}
int yolver(int x, int y){
	int i = yer[x];
	int j = yer[y];
	if(i <= j){
		int ara = qu(j - 1) - qu(i - 1);
		if(ara)
			return -1;
		return j - i;
	}
	int 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("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%d",&git[0][i]);
		amk[i] = git[0][i];
	}

	hazirla();

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

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


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

	for(int i = q; i >= 1; i--){
		if(c[i] == 2){
			int xx = atabul(a[i]);
			int yy = atabul(b[i]);
			if(xx != yy){
				ans.pb(-1);
				continue;
			}
			// cout << a[i] << " " << b[i] << "AMKXX" << endl;
			int l;;
			if(ag[b[i]] != ag[a[i]])
				l = ag[a[i]];
			else
				l = b[i];
			int yol = lca(a[i], l);
			// cout << a[i] << " " << l << " e yol = " << yol << endl;
			if(yol == -1){
				ans.pb(-1);
				continue;
			}
			if(l != b[i]){
				int 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){
				int xx = atabul(a[i]);
				int 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(int i = 0; i < ans.size(); i++)
		printf("%d\n", ans[i]);
	return 0;
}


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

Compilation message

specialg.cpp: In function 'void dfs2(int, int, int)':
specialg.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
specialg.cpp: In function 'int main()':
specialg.cpp:154:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); i++)
                 ~~^~~~~~~~~~~~
specialg.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
specialg.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&git[0][i]);
   ~~~~~^~~~~~~~~~~~~~~~~
specialg.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
specialg.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",c + i, a + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
specialg.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", b + i);
    ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 24312 KB Output isn't correct
2 Halted 0 ms 0 KB -