oj.uz

Submission #157786

# Submission time Handle Problem Language Result Execution time Memory
157786 2019-10-12T22:32:07 Z Lawliet Pictionary (COCI18_pictionary) C++14
140 / 140
 70 ms 2088 KB 
#include <bits/stdc++.h>

using namespace std;

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

int n, m, q;

int sz[MAX];
int pai[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( sz[ U ] < sz[ V ] ) swap( U , V );

	pai[ V ] = U;
	edge[ V ] = W;
	sz[ U ] += sz[ V ];
}

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++)
	{
		sz[ i ] = 1;
		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:71: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 376 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 748 KB Output is correct
2 Correct 35 ms 632 KB Output is correct

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 952 KB Output is correct
2 Correct 27 ms 1016 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1272 KB Output is correct
2 Correct 31 ms 1208 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1360 KB Output is correct
2 Correct 51 ms 1612 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1784 KB Output is correct
2 Correct 59 ms 1960 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 2088 KB Output is correct
2 Correct 68 ms 2080 KB Output is correct