oj.uz

Submission #157785

# Submission time Handle Problem Language Result Execution time Memory
157785 2019-10-12T22:29:26 Z Lawliet Pictionary (COCI18_pictionary) C++17
140 / 140
 69 ms 3008 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX = 100010;
const int INF = 1000000010;

int n, m, q;

int pai[MAX];
int prof[MAX];
int edge[MAX];	

int find(int cur)
{
	if(pai[ cur ] == cur) return cur;
	return find( pai[ cur ] );
}

void join(int U, int V, int W)
{
	U = find( U ); V = find( V );

	if( U == V ) return;

	if( prof[ U ] < prof[ V ] ) swap( U , V );

	pai[ V ] = U;
	edge[ V ] = W;
	if(prof[ U ] == prof[ V ]) prof[ U ]++;
}

int maxPath(int U, int V)
{
	int ans = 0;

	while( U != V )
	{
		if( edge[ U ] < edge[ V ] )
		{
			ans = max(ans , edge[ U ]);
			U = pai[ U ];
		}
		else
		{
			ans = max(ans , edge[ V ]);
			V = pai[ V ];
		}
	}

	return ans;
}

int main()
{
	scanf("%d %d %d",&n,&m,&q);

	for(int i = 1 ; i <= n ; i++)
	{
		pai[ i ] = i;
		edge[ i ] = INF;
	}

	for(int i = m ; i >= 1 ; i--)
		for(int j = i ; j <= n ; j += i) join(i , j , m - i + 1);

	for(int i = 1 ; i <= q ; i++)
	{
		int U, V;
		scanf("%d %d",&U,&V);

		printf("%d\n",maxPath( U , V ));
	}
}

Compilation message

pictionary.cpp: In function 'int main()':
pictionary.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&U,&V);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1144 KB Output is correct
2 Correct 27 ms 1160 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1884 KB Output is correct
2 Correct 34 ms 1440 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1400 KB Output is correct
2 Correct 24 ms 1216 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1404 KB Output is correct
2 Correct 27 ms 1400 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1936 KB Output is correct
2 Correct 32 ms 1576 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2092 KB Output is correct
2 Correct 50 ms 2440 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2684 KB Output is correct
2 Correct 58 ms 2680 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3004 KB Output is correct
2 Correct 65 ms 3008 KB Output is correct