oj.uz

Submission #36790

# Submission time Handle Problem Language Result Execution time Memory
36790 2017-12-14T15:34:11 Z aome ICC (CEOI16_icc) C++14
100 / 100
 193 ms 2216 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

const int N = 105;

int par[N];
vector<int> vec[N];

int find(int u) {
	return (u == par[u]) ? u : par[u] = find(par[u]);
}

void join(int u, int v) {
	u = find(u), v = find(v);
	if (vec[u].size() > vec[v].size()) swap(u, v);
	for (auto i : vec[u]) vec[v].push_back(i);
	par[u] = v, vec[u].clear();
}

bool query(vector<int> a, vector<int> b) {
	int sza = a.size(), szb = b.size();
	int A[N], B[N];
	for (int i = 0; i < sza; ++i) A[i] = a[i];
	for (int i = 0; i < szb; ++i) B[i] = b[i]; 
	return query(sza, szb, A, B);
}

void find(int l, int r, vector<int> &go, vector<int> &to) {
	if (l == r) {
		int tmp = go[l]; go.clear(); go.push_back(tmp); return;
	}
	int mid = (l + r) >> 1;
	vector<int> a, b; b = to;
	for (int i = l; i <= mid; ++i) a.push_back(go[i]);
	if (query(a, b)) find(l, mid, go, to);
	else find(mid + 1, r, go, to);
}

void cal(vector<int> vx, vector<int> vy) {
	find(0, vx.size() - 1, vx, vy);
	find(0, vy.size() - 1, vy, vx);
	setRoad(vx[0], vy[0]), join(vx[0], vy[0]);
}

void run(int n) {
	for (int i = 1; i <= n; ++i) par[i] = i, vec[i].push_back(i);
	while (1) {
		vector<int> go;
		for (int i = 1; i <= n; ++i) {
			if (find(i) == i) go.push_back(i);
		}
		int sz = go.size();
		for (int i = 0; (1 << i) < sz; ++i) {
			vector<int> a, b;
			for (int j = 0; j < sz; ++j) {
				if (j >> i & 1) {
					for (auto k : vec[go[j]]) a.push_back(k);
				}
				else {
					for (auto k : vec[go[j]]) b.push_back(k);
				}
			}
			if (query(a, b)) {
				cal(a, b); break;
			}
		}
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2080 KB Ok! 99 queries used.
2 Correct 6 ms 2076 KB Ok! 94 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2080 KB Ok! 521 queries used.
2 Correct 56 ms 2080 KB Ok! 654 queries used.
3 Correct 49 ms 2084 KB Ok! 652 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 2212 KB Ok! 1419 queries used.
2 Correct 193 ms 2212 KB Ok! 1595 queries used.
3 Correct 163 ms 2212 KB Ok! 1583 queries used.
4 Correct 146 ms 2080 KB Ok! 1514 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 2216 KB Ok! 1454 queries used.
2 Correct 136 ms 2080 KB Ok! 1584 queries used.
3 Correct 146 ms 2080 KB Ok! 1597 queries used.
4 Correct 126 ms 2212 KB Ok! 1482 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 2216 KB Ok! 1581 queries used.
2 Correct 139 ms 2216 KB Ok! 1573 queries used.
3 Correct 156 ms 2084 KB Ok! 1606 queries used.
4 Correct 146 ms 2212 KB Ok! 1567 queries used.
5 Correct 123 ms 2216 KB Ok! 1427 queries used.
6 Correct 133 ms 2216 KB Ok! 1523 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 2208 KB Ok! 1601 queries used.
2 Correct 149 ms 2084 KB Ok! 1611 queries used.