oj.uz

Submission #746222

# Submission time Handle Problem Language Result Execution time Memory
746222 2023-05-22T02:30:13 Z Juan Pictionary (COCI18_pictionary) C++17
140 / 140
 213 ms 3656 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, INF = 0x3f3f3f3f;


struct node{
	int id, pai, edge, sz;
};

struct DSU{
	node v[maxn];

	void init(int n){
		for(int i = 1; i <= n; i++) v[i] = {i, i, INF, 1};
	}

	int find(int x){return (v[x].pai==x ? x : find(v[x].pai));}

	void join(int a, int b, int k){
		a = find(a), b = find(b);
		if(a==b) return;

		if(v[a].sz > v[b].sz) swap(a, b);
		v[a] = {a, b, k, v[a].sz};
		v[b].sz += v[a].sz;
	}

	void query(int a, int b){
		int ans = 0;
		while(a!=b){
			if(v[a].edge < v[b].edge) ans = max(ans, v[a].edge), a = v[a].pai;
			else ans = max(ans, v[b].edge), b = v[b].pai;
		}
		cout << ans << '\n';
	}
}dsu;


int main(){
	int n, m, q; cin >> n >> m >> q;
	dsu.init(n);

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

	while(q--){
		int a, b; cin >> a >> b;
		dsu.query(a, b);
	}
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 384 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 492 KB Output is correct
2 Correct 118 ms 492 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 644 KB Output is correct
2 Correct 151 ms 636 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 1332 KB Output is correct
2 Correct 86 ms 1300 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1556 KB Output is correct
2 Correct 91 ms 1660 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 2144 KB Output is correct
2 Correct 93 ms 1848 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 2484 KB Output is correct
2 Correct 176 ms 2844 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 3012 KB Output is correct
2 Correct 181 ms 3276 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 3532 KB Output is correct
2 Correct 189 ms 3656 KB Output is correct