oj.uz

Submission #400481

# Submission time Handle Problem Language Result Execution time Memory
400481 2021-05-08T06:28:07 Z Lawliet Special graph (IZhO13_specialg) C++17
100 / 100
 158 ms 21576 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;
	indTree[0] = -1;

	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:158:7: warning: unused variable 'dist' [-Wunused-variable]
  158 |   int dist = 0;
      |       ^~~~
specialg.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
specialg.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |   scanf("%d",&tab[0][i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~
specialg.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |  scanf("%d",&qtdQueries);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
specialg.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |   scanf("%d",&type[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
specialg.cpp:135:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  135 |    scanf("%d",&a[i]);
      |    ~~~~~^~~~~~~~~~~~
specialg.cpp:138:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |   if( type[i] == 2 ) scanf("%d %d",&a[i],&b[i]);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 3 ms 972 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 6 ms 972 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 12 ms 1280 KB Output is correct
7 Correct 12 ms 1452 KB Output is correct
8 Correct 12 ms 1356 KB Output is correct
9 Correct 13 ms 1356 KB Output is correct
10 Correct 12 ms 1484 KB Output is correct
11 Correct 146 ms 21064 KB Output is correct
12 Correct 92 ms 14268 KB Output is correct
13 Correct 109 ms 17992 KB Output is correct
14 Correct 88 ms 12868 KB Output is correct
15 Correct 97 ms 14840 KB Output is correct
16 Correct 96 ms 14496 KB Output is correct
17 Correct 122 ms 21572 KB Output is correct
18 Correct 122 ms 21568 KB Output is correct
19 Correct 123 ms 21576 KB Output is correct
20 Correct 158 ms 21072 KB Output is correct