oj.uz

Submission #746220

# Submission time Handle Problem Language Result Execution time Memory
746220 2023-05-22T02:28:58 Z Juan Pictionary (COCI18_pictionary) C++17
56 / 140
 174 ms 1496 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 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 11 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 524 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 1100 KB Output is correct
2 Correct 124 ms 1096 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 1496 KB Output is correct
2 Correct 152 ms 1324 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -