oj.uz

Submission #576930

# Submission time Handle Problem Language Result Execution time Memory
576930 2022-06-13T20:36:02 Z endy Pictionary (COCI18_pictionary) C++14
0 / 140
 1500 ms 21240 KB 
#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--){
		c++;
		for(int j=i ; j<=n ; j+=i){

			if(__gcd(i, j) == i) join(i, j, c);
			//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

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

# Verdict Execution time Memory Grader output
1 Execution timed out 1562 ms 2772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1580 ms 2972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1579 ms 3924 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1585 ms 4352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1582 ms 7296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1579 ms 9124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1584 ms 11980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1569 ms 14552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1575 ms 17344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1574 ms 21240 KB Time limit exceeded
2 Halted 0 ms 0 KB -