Submission #62180

#	Time	Username	Problem	Language	Result	Execution time	Memory
62180		kingpig9	ICC (CEOI16_icc)	C++11	7 / 100	21 ms	800 KiB

icc

#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;
vector<int> verts[MAXN];
int tmpa[MAXN], tmpb[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() {
	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);
		}
	}

	random_shuffle(all(reps));
	//ok while it is true
	vector<int> vfirst;
	for (int i = 1; i < reps.size(); i++) {
		vfirst.push_back(i);
	}
	random_shuffle(all(vfirst));
	for (int vfi = 0; vfi < vfirst.size(); vfi++) {
		int f = vfirst[vfi];
		vector<int> vca, vcb;
		for (int i = 0; i < f; i++) {
			int c = reps[i];
			vca.push_back(c);
		}
		for (int i = f; i < reps.size(); i++) {
			int c = reps[i];
			vcb.push_back(c);
		}

		if (vfi + 1 == vfirst.size() || 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 (stderr)

icc.cpp: In function 'pii findedge()':
icc.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < reps.size(); i++) {
                  ~~^~~~~~~~~~~~~
icc.cpp:77:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int vfi = 0; vfi < vfirst.size(); vfi++) {
                    ~~~~^~~~~~~~~~~~~~~
icc.cpp:84:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = f; i < reps.size(); i++) {
                   ~~^~~~~~~~~~~~~
icc.cpp:89:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (vfi + 1 == vfirst.size() || queryc(vca, vcb)) {
       ~~~~~~~~^~~~~~~~~~~~~~~~
icc.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 7 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10