oj.uz

Submission #604495

# Submission time Handle Problem Language Result Execution time Memory
604495 2022-07-25T07:04:02 Z SeDunion ICC (CEOI16_icc) C++17
100 / 100
 124 ms 508 KB 
#include<algorithm>
#include<iostream>
#include<vector>

#ifndef LOCAL
	#include<icc.h>
#endif

using namespace std;

const int N = 103;

int p[N];

int get(int x) {
	if (x == p[x]) return x;
	return p[x] = get(p[x]);
}

int A[N], B[N];

int rx[N], ry[N], rr;

int road[N][N];

#ifdef LOCAL
void setRoad(int a, int b) {
	if (rx[rr] == a && ry[rr] == b);
	else if (ry[rr] == a && rx[rr] == b);
	else {
		cout << "WRONG\n";
		exit(0);
	}
	++rr;
	cout << "New road " << rx[rr] << " " << ry[rr] << endl;
	road[rx[rr]][ry[rr]] = road[ry[rr]][rx[rr]] = 1;
}
#endif

int query(vector<int>&X, vector<int>&Y) {
#ifdef LOCAL
	cout << "Q: ";
	for (int i : X) cout << i << " ";
	cout << "\n   ";
	for (int i : Y) cout << i << " ";
	cout << endl;
	for (int i : X) for (int j : Y) {
		if (road[i][j]) {
			cout << "TRUE\n";
			return 1;
		}
	}
	cout << "FALSE\n";
	return 0;
#else
	for (int i = 0 ; i < (int)X.size() ; ++ i) A[i] = X[i];
	for (int i = 0 ; i < (int)Y.size() ; ++ i) B[i] = Y[i];
	return query(X.size(), Y.size(), A, B);
#endif
}

void run(int N) {
	for (int i = 1 ; i <= N ; ++ i) p[i] = i;
	for (int rep = 0 ; rep < N - 1 ; ++ rep) {
		vector<int>cur;
		for (int i = 1 ; i <= N ; ++ i) cur.emplace_back(get(i));
		sort(cur.begin(), cur.end()); cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
		int m = cur.size();
		int diff = 0;
#ifdef LOCAL
		cout << "cur ";
		for (int i : cur) cout << i << " ";
		cout << endl;
#endif
		for (int b = 0 ; b < 10 ; ++ b) {
			vector<int>A, B;
			for (int i = 0 ; i < m ; ++ i) {
				if (i >> b & 1) A.emplace_back(cur[i]);
				else B.emplace_back(cur[i]);
			}
			if (A.empty() || B.empty()) continue;
			for (int i = 1 ; i <= N ; ++ i) {
				if (count(A.begin(), A.end(), i) == 0 && count(A.begin(), A.end(), get(i)) == 1) {
					A.emplace_back(i);
				}
				if (count(B.begin(), B.end(), i) == 0 && count(B.begin(), B.end(), get(i)) == 1) {
					B.emplace_back(i);
				}
			}
			int x = query(A, B);
			if (x) diff |= 1 << b;
		}
#ifdef LOCAL
		cout << "diff " << diff << endl;
#endif
		vector<pair<int,int>>can;
		for (int i = 0 ; i < m ; ++ i) {
			int x = cur[i];
			int j = (i ^ diff);
			if (0 <= j && j < m); else continue;
			int y = cur[j];
			if (1 <= y && y <= N) {
				bool has = false;
				for (auto [a, b] : can) {
					if (a == x && b == y) has = true;
					if (a == y && b == x) has = true;
				}
				if (has) continue;
				can.emplace_back(x, y);
			}
		}
		int l = 0, r = (int)can.size() - 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			vector<int>A, B;
			for (int i = 0 ; i <= mid ; ++ i) {
				A.emplace_back(can[i].first);
				B.emplace_back(can[i].second);
			}
			for (int i = 1 ; i <= N ; ++ i) {
				if (count(A.begin(), A.end(), i) == 0 && count(A.begin(), A.end(), get(i)) == 1) {
					A.emplace_back(i);
				}
				if (count(B.begin(), B.end(), i) == 0 && count(B.begin(), B.end(), get(i)) == 1) {
					B.emplace_back(i);
				}
			}
			int x = query(A, B);
			if (x) r = mid;
			else l = mid + 1;
		}
		int x = can[r].first;
		int y = can[r].second;
		vector<int>X, Y;
		for (int i = 1 ; i <= N ; ++ i) {
			if (get(i) == x) X.emplace_back(i);
			if (get(i) == y) Y.emplace_back(i);
		}
		int lx = 0, rx = (int)X.size() - 1;
		while (lx < rx) {
			int mid = (lx + rx) >> 1;
			vector<int>A, B = Y;
			for (int i = 0 ; i <= mid ; ++ i) {
				A.emplace_back(X[i]);
			}
			int x = query(A, B);
			if (x) rx = mid;
			else lx = mid + 1;
		}
		int ly = 0, ry = (int)Y.size() - 1;
		while (ly < ry) {
			int mid = (ly + ry) >> 1;
			vector<int>A = X, B;
			for (int i = 0 ; i <= mid ; ++ i) {
				B.emplace_back(Y[i]);
			}
			int x = query(A, B);
			if (x) ry = mid;
			else ly = mid + 1;
		}
		int a = X[rx];
		int b = Y[ry];
#ifdef LOCAL
		cout << "GUESS ROAD " << a << " " << b << endl;
#endif
		p[get(a)] = get(b);
		setRoad(a, b);
	}
}

#ifdef LOCAL
int main() {
	int n;
	cin >> n;
	for (int rep = 0 ; rep < n - 1 ; ++ rep) {
		cin >> rx[rep] >> ry[rep];
	}
	road[rx[0]][ry[0]] = road[ry[0]][rx[0]] = 1;
	run(n);
}
#endif

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 109 queries used.
2 Correct 5 ms 468 KB Ok! 101 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 496 KB Ok! 583 queries used.
2 Correct 27 ms 484 KB Ok! 512 queries used.
3 Correct 30 ms 468 KB Ok! 572 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 468 KB Ok! 1497 queries used.
2 Correct 100 ms 468 KB Ok! 1364 queries used.
3 Correct 104 ms 492 KB Ok! 1417 queries used.
4 Correct 112 ms 492 KB Ok! 1449 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 480 KB Ok! 1386 queries used.
2 Correct 103 ms 488 KB Ok! 1383 queries used.
3 Correct 108 ms 468 KB Ok! 1395 queries used.
4 Correct 104 ms 432 KB Ok! 1403 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 508 KB Ok! 1371 queries used.
2 Correct 118 ms 488 KB Ok! 1363 queries used.
3 Correct 116 ms 488 KB Ok! 1392 queries used.
4 Correct 105 ms 484 KB Ok! 1396 queries used.
5 Correct 107 ms 488 KB Ok! 1493 queries used.
6 Correct 108 ms 484 KB Ok! 1526 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 484 KB Ok! 1394 queries used.
2 Correct 95 ms 432 KB Ok! 1364 queries used.