oj.uz

답안 #62187

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
62187 2018-07-27T18:58:05 Z kingpig9 CEOI16_icc (CEOI16_icc) C++11
61 / 100
 220 ms 848 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() {
#warning reset!
	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);
		}
	}

	//ok while it is true
	while (true) {
		random_shuffle(all(reps));
		int f = reps.size() / 2;
		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 (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:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = f; i < reps.size(); i++) {
                   ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 504 KB Ok! 106 queries used.
2 Correct 9 ms 700 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 700 KB Ok! 541 queries used.
2 Correct 106 ms 700 KB Ok! 850 queries used.
3 Correct 71 ms 700 KB Ok! 816 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 700 KB Ok! 1519 queries used.
2 Correct 213 ms 800 KB Ok! 2134 queries used.
3 Correct 185 ms 800 KB Ok! 1754 queries used.
4 Correct 162 ms 800 KB Ok! 1663 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 800 KB Ok! 1636 queries used.
2 Correct 177 ms 848 KB Ok! 1665 queries used.
3 Correct 195 ms 848 KB Ok! 1877 queries used.
4 Correct 163 ms 848 KB Ok! 1593 queries used.

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 220 ms 848 KB Too many queries! 1934 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 204 ms 848 KB Too many queries! 1893 out of 1625
2 Halted 0 ms 0 KB -