oj.uz

Submission #92603

# Submission time Handle Problem Language Result Execution time Memory
92603 2019-01-04T03:23:37 Z sidiq_ha Pictionary (COCI18_pictionary) C++14
140 / 140
 377 ms 16628 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int nn = 1e5 + 5;
int p[nn], ranke[nn], L[nn], R[nn], ans[nn];
vector<int> query[nn];

struct pasangan {
	int c1;
	int c2;
};

pasangan arr[nn];

int findSet(int nod) {
	if (p[nod] == nod) return nod;
	else return p[nod] = findSet(p[nod]);
}

bool cek(int n1, int n2) {
	n1 = findSet(n1);
	n2 = findSet(n2);
	if (n1 == n2) return 1;
	else return 0;
}

void gabung(int n1, int n2) {
	n1 = findSet(n1);
	n2 = findSet(n2);
	if (ranke[n1] < ranke[n2]) {
		p[n1] = n2;
	} else {
		p[n2] = n1;
		if (ranke[n1] == ranke[n2]) ranke[n1]++;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N, M, Q;
	cin >> N >> M >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> arr[i].c1 >> arr[i].c2;
		L[i] = 1, R[i] = M;
		ans[i] = -1;
	}
	bool iterasi = 1;
	while (iterasi) {
		iterasi = 0;
		for (int i = 1; i <= N; i++) {
			p[i] = i;
			ranke[i] = 0;
		}
		for (int i = 1; i <= M; i++) {
			query[i].clear();
		}
		for (int i = 1; i <= Q; i++) {
			/*cout << L[i] << ' ' << R[i] << "\n";*/
			if (L[i] <= R[i]) {
				iterasi = 1;
				query[(L[i] + R[i]) >> 1].push_back(i);
			}
		}
		/*cout << "\n";*/
		for (int i = 1; i <= M; i++) {
			int j = 2;
			while (j * (M - i + 1) <= N) {
				if (!cek(M - i + 1, j * (M - i + 1)))
					gabung(M - i + 1, j * (M - i + 1));	
				j++;
			}
			int l1 = query[i].size();
			for (j = 0; j < l1; j++) {
				int idx = query[i][j];
				if (cek(arr[idx].c1, arr[idx].c2)) {
					ans[idx] = i;
					R[idx] = i - 1;
				} else L[idx] = i + 1;
			}
		}
	}
	for (int i = 1; i <= Q; i++) {
		cout << ans[i] << "\n";
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3064 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3960 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7772 KB Output is correct
2 Correct 28 ms 6900 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9796 KB Output is correct
2 Correct 41 ms 8704 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 7860 KB Output is correct
2 Correct 62 ms 7468 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 8484 KB Output is correct
2 Correct 61 ms 7440 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 11124 KB Output is correct
2 Correct 117 ms 8384 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 9332 KB Output is correct
2 Correct 194 ms 12480 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 14368 KB Output is correct
2 Correct 377 ms 13300 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 16628 KB Output is correct
2 Correct 277 ms 14964 KB Output is correct