oj.uz

Submission #706937

# Submission time Handle Problem Language Result Execution time Memory
706937 2023-03-08T06:52:40 Z SanguineChameleon ICC (CEOI16_icc) C++17
90 / 100
 146 ms 596 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

#ifndef KAMIRULEZ

#include <icc.h>

#endif

using namespace std;

#ifdef KAMIRULEZ

int pt = 0;
pair<int, int> e[120];
bool f[120][120];

int query(int size_a, int size_b, int a[], int b[]) {
	for (int i = 0; i < size_a; i++) {
		int u = a[i];
		for (int j = 0; j < size_b; j++) {
			int v = b[j];
			assert(u != v);
		}
	}
	for (int i = 0; i < size_a; i++) {
		int u = a[i];
		for (int j = 0; j < size_b; j++) {
			int v = b[j];
			if (f[u][v]) {
				return 1;
			}
		}
	}
	return 0;
}

void add() {
	int u = e[pt].first;
	int v = e[pt].second;
	f[u][v] = true;
	f[v][u] = true;
}

void setRoad(int u, int v) {
	assert(((e[pt].first == u) && (e[pt].second == v)) || ((e[pt].first == v) && (e[pt].second == u)));
	pt++;
	add();
}

#endif

ostream& operator<<(ostream &out, vector<int> q) {
	int sz = q.size();
	for (int i = 0; i < sz; i++) {
		out << q[i];
		if (i < sz - 1) {
			out << " ";
		}
	}
	return out;
}

int query_vec(vector<int> A, vector<int> B) {
	int a[120] = {};
	int b[120] = {};
	int size_a = A.size();
	int size_b = B.size();
	for (int i = 0; i < size_a; i++) {
		a[i] = A[i];
	}
	for (int i = 0; i < size_b; i++) {
		b[i] = B[i];
	}
	return query(size_a, size_b, a, b);
}

void run(int n) {
	vector<vector<int>> comps;
	for (int i = 1; i <= n; i++) {
		comps.push_back({i});
	}
	for (int k = 0; k < n - 1; k++) {
		vector<int> orig(n - k);
		iota(orig.begin(), orig.end(), 0);
		vector<vector<int>> cur = {orig};
		shuffle(cur.begin(), cur.end(), gen);
		while (true) {
			vector<vector<int>> nxt;
			vector<int> ql;
			vector<int> qr;
			for (auto x: cur) {
				int sz = x.size();
				vector<int> lv(x.begin(), x.begin() + sz / 2);
				vector<int> rv(x.begin() + sz / 2, x.end());
				if (!lv.empty()) {
					nxt.push_back(lv);
					for (auto id: lv) {
						ql.insert(ql.end(), comps[id].begin(), comps[id].end());
					}
				}
				if (!rv.empty()) {
					nxt.push_back(rv);
					for (auto id: rv) {
						qr.insert(qr.end(), comps[id].begin(), comps[id].end());
					}
				}
			}
			if (query_vec(ql, qr)) {
				shuffle(ql.begin(), ql.end(), gen);
				shuffle(qr.begin(), qr.end(), gen);
				while (true) {
					int sz = ql.size();
					if (sz == 1) {
						break;
					}
					vector<int> lv(ql.begin(), ql.begin() + sz / 2);
					vector<int> rv(ql.begin() + sz / 2, ql.end());
					if (!lv.empty() && query_vec(lv, qr)) {
						ql = lv;
					}
					else {
						ql = rv;
					}
				}
				while (true) {
					int sz = qr.size();
					if (sz == 1) {
						break;
					}
					vector<int> lv(qr.begin(), qr.begin() + sz / 2);
					vector<int> rv(qr.begin() + sz / 2, qr.end());
					if (!lv.empty() && query_vec(lv, ql)) {
						qr = lv;
					}
					else {
						qr = rv;
					}
				}
				int u = ql[0];
				int v = qr[0];
				int cu = -1;
				int cv = -1;
				for (int i = 0; i < n - k; i++) {
					for (auto x: comps[i]) {
						if (u == x) {
							cu = i;
							break;
						}
					}
				}
				for (int i = 0; i < n - k; i++) {
					for (auto x: comps[i]) {
						if (v == x) {
							cv = i;
							break;
						}
					}
				}
				comps[cu].insert(comps[cu].end(), comps[cv].begin(), comps[cv].end());
				comps.erase(comps.begin() + cv);
				setRoad(u, v);
				break;
			}
			else {
				cur.swap(nxt);
			}
		}
	}
}

#ifdef KAMIRULEZ

int main() {
	freopen("kamirulez.inp", "r", stdin);
	freopen("kamirulez.out", "w", stdout);
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		e[i] = {u, v};
	}
	add();
	run(n);
}

#endif

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 504 KB Ok! 556 queries used.
2 Correct 38 ms 496 KB Ok! 670 queries used.
3 Correct 36 ms 468 KB Ok! 669 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 516 KB Ok! 1395 queries used.
2 Correct 124 ms 520 KB Ok! 1646 queries used.
3 Correct 108 ms 512 KB Ok! 1526 queries used.
4 Correct 109 ms 468 KB Ok! 1529 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 524 KB Ok! 1480 queries used.
2 Correct 106 ms 516 KB Ok! 1491 queries used.
3 Correct 116 ms 596 KB Ok! 1622 queries used.
4 Correct 102 ms 520 KB Ok! 1430 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 532 KB Ok! 1592 queries used.
2 Correct 146 ms 528 KB Ok! 1647 queries used.
3 Correct 122 ms 592 KB Ok! 1677 queries used.
4 Correct 114 ms 524 KB Ok! 1621 queries used.
5 Correct 118 ms 512 KB Ok! 1474 queries used.
6 Correct 120 ms 512 KB Ok! 1580 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 520 KB Too many queries! 1632 out of 1625
2 Halted 0 ms 0 KB -