Submission #576984

#	Time	Username	Problem	Language	Result	Execution time	Memory
576984		endy	Pictionary (COCI18_pictionary)	C++14	140 / 140	251 ms	24636 KiB

pictionary

#include <bits/stdc++.h>
#define MAX 200010

using namespace std;

int n, m, q, pai[MAX], sz[MAX], maxi, h[MAX], anc[MAX][30], bla[MAX][2], mark[MAX];
vector < pair <int,int> > g[MAX];

void init(int x){

	for(int i=1 ; i<=x ; i++){
		pai[i] = i;
		sz[i]=1;
		h[i] = -1;
	}

	return;
}

int find(int x){

	if(pai[x] == x) return x;

	return find(pai[x]);
}

void join(int x, int y, int c){

	x = find(x), y = find(y);

	if(x == y) return;

	if(sz[x] > sz[y]) swap(x,y);

	pai[x] = y;
	sz[y] += sz[x];
	g[x].push_back(make_pair(y,c));
	g[y].push_back(make_pair(x,c));

	return;

}

void dfs(int x){

	for(int i=0 ; i<g[x].size() ; i++){

		int v = g[x][i].first;

		if(h[v] == -1){

			h[v] = h[x]+1;
			anc[v][0] = pai[v];
			dfs(v);
		}
	}
}

int lca(int x, int y){

	if(h[x] > h[y]) swap(x,y);

	for(int i=24 ; i>=0 ; i--){

		if(h[y] - (1 << i) >= h[x]) y = anc[y][i]; 
	}

	if(x == y) return x;

	for(int i=24 ; i>=0 ; i--){

		if(anc[x][i] != anc[y][i]){

			x = anc[x][i];
			y = anc[y][i];
		}
	}

	return anc[x][0];
}

int main(){

	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m >> q;

	init(n);

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

	for(int i=1 ; i<=n ; i++){

		int k = find(i);

		if(mark[k] == 0) {
			mark[k] = 1;
			h[k] = 0;
			dfs(k);
		}
	}

	for(int i=1 ; i<25 ; i++){
		for(int j=1 ; j<=n ; j++){

			anc[j][i] = anc[anc[j][i-1]][i-1];
		}
	}

	for(int i=0 ; i<q ; i++){

		int a, b;
		cin >> a >> b;

		bla[i][0] = a;
		bla[i][1] = b;
	}

	for(int i=0 ; i<q ; i++){

		int maxa=0, maxb=0;

		int a = bla[i][0];
		int b = bla[i][1];

		int l = lca(a,b);

		//cout << "lca:" << l << endl;
	
		while(a != l){

			if(pai[a] == a){
				maxa = -1;
				break;
			}

			for(int i=0 ; i<g[a].size() ; i++){

				if(g[a][i].first == pai[a]){
					maxa = max(maxa, g[a][i].second);
				}
			}

			a = pai[a];

		}

		while(b != l){

			if(pai[b] == b){
				maxb = -1;
				break;
			}

			for(int i=0 ; i<g[b].size() ; i++){

				if(g[b][i].first == pai[b]){
					maxa = max(maxa, g[b][i].second);
				}
			}

			b = pai[b];

		}

		maxi = max(maxa, maxb);

		if(maxa == -1 || maxb == -1) maxi=-1;

		cout << maxi << endl;
		
	}

	return 0;
}

Compilation message (stderr)

pictionary.cpp: In function 'void dfs(int)':
pictionary.cpp:46:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0 ; i<g[x].size() ; i++){
      |                ~^~~~~~~~~~~~
pictionary.cpp: In function 'int main()':
pictionary.cpp:141:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |    for(int i=0 ; i<g[a].size() ; i++){
      |                  ~^~~~~~~~~~~~
pictionary.cpp:159:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |    for(int i=0 ; i<g[b].size() ; i++){
      |                  ~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14