oj.uz

Submission #62217

# Submission time Handle Problem Language Result Execution time Memory
62217 2018-07-27T21:28:20 Z kingpig9 ICC (CEOI16_icc) C++11
100 / 100
 195 ms 892 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "icc.h"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> using ordset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int MAXN = 110;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

struct union_find {
	int par[MAXN];

	void init() {
		for (int i = 0; i < MAXN; i++) {
			par[i] = i;
		}
	}

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

	void merge (int x, int y) {
		par[find(x)] = find(y);
	}
} uf;

int N;
int tmpa[MAXN], tmpb[MAXN];
vector<int> verts[MAXN];

int query (vector<int> a, vector<int> b) {
	copy(all(a), tmpa);
	copy(all(b), tmpb);
	return query(a.size(), b.size(), tmpa, tmpb);
}

vector<int> getverts (vector<int> vc) {
	vector<int> v;
	for (int c : vc) {
		v.insert(v.end(), all(verts[c]));
	}
	return v;
}

int queryc (vector<int> ca, vector<int> cb) {
	return query(getverts(ca), getverts(cb));
}

pii findedge() {
#warning reset!
	for (int i = 1; i <= N; i++) {
		verts[i].clear();
	}
	vector<int> reps;
	for (int i = 1; i <= N; i++) {
		verts[uf.find(i)].push_back(i);
		if (i == uf.find(i)) {
			reps.push_back(i);
		}
	}

	//ok while it is true
	//which bit does it differ in?
	int xoedge = 0;	//xor of edge
	int nbt = 7;
	for (int bt = 0; bt < 7; bt++) {
		//bt = bit that it differs by
		vector<int> vca, vcb;
		for (int i = 0; i < reps.size(); i++) {
			if (i & (1 << bt)) {
				vca.push_back(reps[i]);
			} else {
				vcb.push_back(reps[i]);
			}
		}

		if (!vca.empty() && !vcb.empty()) {
			xoedge ^= (queryc(vca, vcb) << bt);
		} else {
			nbt = bt;
			break;
		}
	}

	int bd = __builtin_ctz(xoedge);	//bit that is different
	int cmpa = 0, cmpb = (1 << bd);
	for (int bt = 0; bt < nbt; bt++) {
		if (bt == bd) {
			continue;
		}

		vector<int> vca, vcb;
		if (xoedge & (1 << bt)) {
			//they differ in this bit
			for (int i = 0; i < reps.size(); i++) {
				int bibt = (i >> bt) & 1;	//bit of i that is at position bt
				int bibd = (i >> bd) & 1;	//bit of i that is at position bd
				if (bibt == 0 && bibd == 0) {
					vca.push_back(reps[i]);
				} else if (bibt == 1 && bibd == 1) {
					vcb.push_back(reps[i]);
				}
			}

			if (queryc(vca, vcb)) {
				//then yes. cmpa has this bit as 0, cmpb has this bit as 1.
				cmpb ^= (1 << bt);
			} else {
				cmpa ^= (1 << bt);
			}
		} else {
			//they are same in this bit. is it zero or one?
			for (int i = 0; i < reps.size(); i++) {
				int bibt = (i >> bt) & 1;	//bit of i that is at position bt
				int bibd = (i >> bd) & 1;	//bit of i that is at position bd
				if (bibt == 0) {
					if (bibd == 0) {
						vca.push_back(reps[i]);
					} else {
						vcb.push_back(reps[i]);
					}
				}
			}

			if (queryc(vca, vcb)) {
				//"bt" is zero
			} else {
				//"bt" is one
				cmpa ^= (1 << bt);
				cmpb ^= (1 << bt);
			}
		}
	}

	vector<int> va = verts[reps[cmpa]], vb = verts[reps[cmpb]];;
	while (va.size() > 1) {
		int half = va.size() / 2;
		if (query(vector<int> (va.begin(), va.begin() + half), vb)) {
			va.resize(half);
		} else {
			va.erase(va.begin(), va.begin() + half);
		}
	}

	while (vb.size() > 1) {
		int half = vb.size() / 2;
		if (query(va, vector<int> (vb.begin(), vb.begin() + half))) {
			vb.resize(half);
		} else {
			vb.erase(vb.begin(), vb.begin() + half);
		}
	}

	//ok now we have the components
	//get down to vertices
	return pii(va[0], vb[0]);
}

void run (int nnnnn) {
	N = nnnnn;
	uf.init();
	//just randomize it lol
	for (int i = 0; i < N - 1; i++) {
		pii p = findedge();
		setRoad(p.fi, p.se);
		uf.merge(p.fi, p.se);
	}
}

Compilation message

icc.cpp:62:2: warning: #warning reset! [-Wcpp]
 #warning reset!
  ^~~~~~~
icc.cpp: In function 'pii findedge()':
icc.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < reps.size(); i++) {
                   ~~^~~~~~~~~~~~~
icc.cpp:107:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < reps.size(); i++) {
                    ~~^~~~~~~~~~~~~
icc.cpp:125:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < reps.size(); i++) {
                    ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 504 KB Ok! 117 queries used.
2 Correct 11 ms 504 KB Ok! 117 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 776 KB Ok! 646 queries used.
2 Correct 46 ms 776 KB Ok! 552 queries used.
3 Correct 48 ms 776 KB Ok! 591 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 800 KB Ok! 1572 queries used.
2 Correct 144 ms 800 KB Ok! 1372 queries used.
3 Correct 195 ms 812 KB Ok! 1613 queries used.
4 Correct 173 ms 876 KB Ok! 1575 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 876 KB Ok! 1583 queries used.
2 Correct 156 ms 880 KB Ok! 1544 queries used.
3 Correct 155 ms 880 KB Ok! 1488 queries used.
4 Correct 190 ms 880 KB Ok! 1609 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 880 KB Ok! 1414 queries used.
2 Correct 172 ms 880 KB Ok! 1433 queries used.
3 Correct 150 ms 880 KB Ok! 1424 queries used.
4 Correct 158 ms 892 KB Ok! 1452 queries used.
5 Correct 183 ms 892 KB Ok! 1601 queries used.
6 Correct 159 ms 892 KB Ok! 1602 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 892 KB Ok! 1448 queries used.
2 Correct 144 ms 892 KB Ok! 1420 queries used.