Submission #92603

#	Time	Username	Problem	Language	Result	Execution time	Memory
92603		sidiq_ha	Pictionary (COCI18_pictionary)	C++14	140 / 140	377 ms	16628 KiB

pictionary

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14