oj.uz

Submission #62181

# Submission time Handle Problem Language Result Execution time Memory
62181 2018-07-27T18:31:16 Z kingpig9 ICC (CEOI16_icc) C++11
18 / 100
 573 ms 820 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;
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[i].clear();
	}
	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

icc.cpp: In function 'pii findedge()':
icc.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < reps.size(); i++) {
                  ~~^~~~~~~~~~~~~
icc.cpp:80:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int vfi = 0; vfi < vfirst.size(); vfi++) {
                    ~~~~^~~~~~~~~~~~~~~
icc.cpp:87:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = f; i < reps.size(); i++) {
                   ~~^~~~~~~~~~~~~
icc.cpp:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (vfi + 1 == vfirst.size() || queryc(vca, vcb)) {
       ~~~~~~~~^~~~~~~~~~~~~~~~
icc.cpp:118: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 14 ms 504 KB Ok! 141 queries used.
2 Correct 16 ms 740 KB Ok! 128 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 740 KB Ok! 1095 queries used.
2 Correct 143 ms 740 KB Ok! 1604 queries used.
3 Correct 148 ms 740 KB Ok! 1591 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 573 ms 796 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 452 ms 796 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 383 ms 800 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 419 ms 820 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -