Submission #576977

#	Time	Username	Problem	Language	Result	Execution time	Memory
576977		endy	Pictionary (COCI18_pictionary)	C++14	0 / 140	1589 ms	21760 KiB

pictionary

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

using namespace std;

int n, m, q, c=0, pai[MAX], sz[MAX], h[MAX], que[MAX][2], anc[MAX][30], maxi, edge[MAX];
vector <int> g[MAX];

void init(int x){

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

		pai[i]=i;
		sz[i]=1;
		h[i]=-1;
	}
}

int find(int x){

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

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

	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];
	edge[x] = k;
	g[x].push_back(y);
	g[y].push_back(x);
	
}

void dfs(int x){

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

		int v=g[x][i];

		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);
			//cout << __gcd(i, j) << endl;
		}
	}

	for(int i=0 ; i<q ; i++) cin >> que[i][0] >> que[i][1];

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

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

			h[i] = 0;
			dfs(i);
		}
	}

	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=que[i][0], b=que[i][1], maxa=0, maxb=0;

		int l = lca(a,b);

		while(a != l){

			maxa=max(maxa, edge[a]);
			a = pai[a];
		}

		while(b != l){

			maxb=max(maxb, edge[b]);
			b = pai[b];
		}

		cout << max(maxa, maxb) << endl;


	}

	return 0;

}

Compilation message (stderr)

pictionary.cpp: In function 'void dfs(int)':
pictionary.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i=0 ; i < g[x].size() ; i++){
      |                ~~^~~~~~~~~~~~~

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