oj.uz

Submission #62198

# Submission time Handle Problem Language Result Execution time Memory
62198 2018-07-27T19:58:21 Z kingpig9 ICC (CEOI16_icc) C++11
90 / 100
 208 ms 904 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?
	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 (queryc(vca, vcb)) {
			//then great you have it
			vector<int> va = getverts(vca), vb = getverts(vcb);
			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:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < reps.size(); i++) {
                   ~~^~~~~~~~~~~~~
icc.cpp:113:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 96 queries used.
2 Correct 9 ms 504 KB Ok! 99 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 540 KB Ok! 530 queries used.
2 Correct 53 ms 716 KB Ok! 684 queries used.
3 Correct 57 ms 728 KB Ok! 672 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 792 KB Ok! 1446 queries used.
2 Correct 200 ms 792 KB Ok! 1665 queries used.
3 Correct 208 ms 816 KB Ok! 1593 queries used.
4 Correct 161 ms 844 KB Ok! 1490 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 844 KB Ok! 1488 queries used.
2 Correct 150 ms 872 KB Ok! 1518 queries used.
3 Correct 153 ms 892 KB Ok! 1639 queries used.
4 Correct 153 ms 892 KB Ok! 1527 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 892 KB Ok! 1636 queries used.
2 Correct 164 ms 892 KB Ok! 1609 queries used.
3 Correct 159 ms 892 KB Ok! 1633 queries used.
4 Correct 176 ms 892 KB Ok! 1592 queries used.
5 Correct 142 ms 892 KB Ok! 1497 queries used.
6 Correct 149 ms 904 KB Ok! 1565 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 904 KB Too many queries! 1629 out of 1625
2 Halted 0 ms 0 KB -