oj.uz

Submission #362025

# Submission time Handle Problem Language Result Execution time Memory
362025 2021-02-01T15:13:46 Z Lawliet Special graph (IZhO13_specialg) C++17
0 / 100
 3 ms 876 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;

const int LOG = 20;
const int MAXN = 100010;
const int INF = 1000000010;

int n, qtdQueries;

int ans[MAXN];
int mn[LOG][MAXN];
int tab[LOG][MAXN];
int inDegree[MAXN];
int type[MAXN], a[MAXN], b[MAXN];

int posCycle[MAXN];
int indCycle[MAXN], szCycle[MAXN];
int treeDepth[MAXN], indTree[MAXN];

bool mark[MAXN];

vector<int> ord;

queue<int> q;

void add(int cur)
{
	q.push( cur );
	mark[cur] = true;
}

void topologicalSorting()
{
	for(int i = 1 ; i <= n ; i++)
		inDegree[ tab[0][i] ]++;

	for(int i = 1 ; i <= n ; i++)
		if( inDegree[i] == 0 ) add( i );

	while( !q.empty() )
	{
		int cur = q.front();
		q.pop();

		ord.push_back( cur );

		if( --inDegree[ tab[0][cur] ] == 0 )
			add( tab[0][cur] );
	}

	int qtdCycles = 0;

	for(int i = 1 ; i <= n ; i++)
	{
		if( mark[i] ) continue;

		int cur = i, pos = 0;
		qtdCycles++;

		while( !mark[cur] )
		{
			mark[cur] = true;

			szCycle[qtdCycles]++;
			posCycle[cur] = pos++;
			indCycle[cur] = qtdCycles;

			cur = tab[0][cur];
		}
	}

	int qtdTrees = 0;

	while( !ord.empty() )
	{
		int cur = ord.back();
		ord.pop_back();

		if( indCycle[ tab[0][cur] ] != 0 ) indTree[cur] = ++qtdTrees;
		else indTree[cur] = indTree[ tab[0][cur] ];

		treeDepth[cur] = treeDepth[ tab[0][cur] ] + 1;
	}
}

int jump(int node, int k)
{
	for(int i = 0 ; i < LOG ; i++)
		if( k & (1 << i) ) node = tab[i][node];

	return node;
}

int getMin(int node, int k)
{
	int ans = INF;

	for(int i = 0 ; i < LOG ; i++)
	{
		if( k & (1 << i) )
		{
			ans = min( ans , mn[i][node] );
			node = tab[i][node];
		}
	}

	return ans;
}

void solveTestCase()
{
	scanf("%d",&n);

	for(int i = 1 ; i <= n ; i++)
		scanf("%d",&tab[0][i]);

	for(int i = 1 ; i <= n ; i++)
		mn[0][i] = INF;

	for(int i = 0 ; i < LOG ; i++)
		mn[i][0] = INF;

	scanf("%d",&qtdQueries);

	for(int i = 1 ; i <= qtdQueries ; i++)
	{
		scanf("%d",&type[i]);

		if( type[i] == 1 )
		{
			scanf("%d",&a[i]);
			mn[0][ a[i] ] = i;
		}
		if( type[i] == 2 ) scanf("%d %d",&a[i],&b[i]);
	}

	for(int k = 1 ; k < LOG ; k++)
	{
		for(int i = 1 ; i <= n ; i++)
		{
			int jump = tab[k - 1][i];

			tab[k][i] = tab[k - 1][jump];
			mn[k][i] = min( mn[k - 1][i] , mn[k - 1][jump] );
		}
	}

	topologicalSorting();

	for(int i = 1 ; i <= qtdQueries ; i++)
	{
		if( type[i] == 1 ) continue;

		int dist = 0;
		int A = a[i], B = b[i];

		if( indTree[A] != 0 && indTree[A] == indTree[B] )
		{
			int jumpA = jump( A , treeDepth[A] - treeDepth[B] );

			if( jumpA != B ) ans[i] = -1;
			else ans[i] = treeDepth[A] - treeDepth[B];

			continue;
		}

		int t = jump( A , MAXN );
		int root = jump( A , treeDepth[A] );

		if( t == 0 || indCycle[t] != indCycle[B] )
		{
			ans[i] = -1;
			continue;
		}
		
		ans[i] = posCycle[B] - posCycle[root];
		if( ans[i] < 0 ) ans[i] += szCycle[ indCycle[root] ];

		ans[i] += treeDepth[A];
	}

	for(int i = 1 ; i <= qtdQueries ; i++)
	{
		if( type[i] == 1 ) continue;

		if( ans[i] == -1 ) printf("-1\n");
		else if( getMin( a[i] , ans[i] ) < i ) printf("-1\n");
		else printf("%d\n",ans[i]);
	}
}

int main()
{
	int t = 1;
	// scanf("%d",&t);

	while( t-- )
		solveTestCase();
}

Compilation message

specialg.cpp: In function 'void solveTestCase()':
specialg.cpp:157:7: warning: unused variable 'dist' [-Wunused-variable]
  157 |   int dist = 0;
      |       ^~~~
specialg.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
specialg.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |   scanf("%d",&tab[0][i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~
specialg.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |  scanf("%d",&qtdQueries);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
specialg.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |   scanf("%d",&type[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
specialg.cpp:134:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  134 |    scanf("%d",&a[i]);
      |    ~~~~~^~~~~~~~~~~~
specialg.cpp:137:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |   if( type[i] == 2 ) scanf("%d %d",&a[i],&b[i]);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

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