oj.uz

Submission #576984

# Submission time Handle Problem Language Result Execution time Memory
576984 2022-06-13T21:03:26 Z endy Pictionary (COCI18_pictionary) C++14
140 / 140
 251 ms 24636 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5076 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5304 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 5888 KB Output is correct
2 Correct 100 ms 6448 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 6388 KB Output is correct
2 Correct 135 ms 6952 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 9324 KB Output is correct
2 Correct 80 ms 9868 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 10952 KB Output is correct
2 Correct 106 ms 12376 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 13616 KB Output is correct
2 Correct 99 ms 14432 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 16388 KB Output is correct
2 Correct 182 ms 18972 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 19344 KB Output is correct
2 Correct 225 ms 22508 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 23228 KB Output is correct
2 Correct 245 ms 24636 KB Output is correct