| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 86209 |
2018-11-25T13:14:16 Z |
JustInCase |
ICC (CEOI16_icc) |
C++17 |
|
3 ms |
552 KB |
#include <bits/stdc++.h>
#include "icc.h"
#define Run run
#define Query query
#define SetRoad setRoad
#define int32_t int
const int32_t MAX_N = 100;
int32_t parent[MAX_N + 5], size[MAX_N + 5];
int32_t FindParent(int32_t x) {
if(parent[x] == x) {
return x;
}
else {
parent[x] = FindParent(parent[x]);
return parent[x];
}
}
void Unite(int32_t x, int32_t y) {
int32_t parX = FindParent(x);
int32_t parY = FindParent(y);
if(parX == parY) {
return;
}
if(size[parX] <= size[parY]) {
parent[parX] = parY;
size[parY] += size[parX];
}
else {
parent[parY] = parX;
size[parX] += size[parY];
}
}
int32_t Query(int32_t sizeA, int32_t sizeB, int32_t *a, int32_t *b);
void SetRoad(int32_t a, int32_t b);
void Run(int32_t n) {
for(int32_t i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
bool isBitDiff[10];
int32_t sizeA, sizeB, a[MAX_N + 5], b[MAX_N + 5], aCpy[MAX_N + 5];
int32_t compInd[MAX_N + 5];
for(int32_t q = 0; q < n - 1; q++) {
int32_t cntComps = 0;
for(int32_t i = 0; i < n; i++) {
if(parent[i] == i) {
compInd[i] = cntComps;
cntComps++;
}
}
std::vector< int32_t > comps[MAX_N + 5];
for(int32_t i = 0; i < n; i++) {
comps[compInd[FindParent(i)]].push_back(i);
}
memset(isBitDiff, 0, sizeof(isBitDiff));
int32_t comp1 = -1;
for(int32_t j = 0; (1 << j) < cntComps; j++) {
sizeA = 0;
sizeB = 0;
std::vector< int32_t > aComps;
for(int32_t p = 0; p < cntComps; p++) {
if((p & (1 << j)) == 0) {
aComps.push_back(p);
for(auto &x : comps[p]) {
a[sizeA] = x;
sizeA++;
}
}
else {
for(auto &x : comps[p]) {
b[sizeB] = x;
sizeB++;
}
}
}
if(Query(sizeA, sizeB, a, b) == 1) {
isBitDiff[j] = true;
if(comp1 == -1) {
int32_t low = 0, high = aComps.size() - 1;
while(low <= high) {
if(low == high) {
comp1 = aComps[low];
break;
}
int32_t mid = (low + high) / 2;
sizeA = 0;
for(int32_t i = low; i <= mid; i++) {
for(auto &x : comps[aComps[i]]) {
a[sizeA] = x;
sizeA++;
}
}
if(Query(sizeA, sizeB, a, b) == 1) {
high = mid - 1;
if(low == mid) {
comp1 = aComps[low];
break;
}
}
else {
low = mid + 1;
if(mid + 1 == high) {
comp1 = aComps[mid + 1];
break;
}
}
}
}
}
}
int32_t comp2 = comp1;
for(int32_t i = 0; (1 << i) < cntComps; i++) {
if(isBitDiff[i]) {
comp2 ^= (1 << i);
}
}
std::cout << comp1 << " " << comp2 << '\n';
sizeB = 0;
for(auto &x : comps[comp2]) {
b[sizeB] = x;
sizeB++;
}
int32_t u;
int32_t low = 0, high = comps[comp1].size() - 1;
while(low <= high) {
if(low == high) {
u = comps[comp1][low];
break;
}
int32_t mid = (low + high) / 2;
sizeA = 0;
for(int32_t i = low; i <= mid; i++) {
a[sizeA] = comps[comp1][i];
sizeA++;
}
if(Query(sizeA, sizeB, a, b) == 1) {
high = mid - 1;
if(low == mid) {
u = a[low];
break;
}
}
else {
low = mid + 1;
if(mid + 1 == high) {
u = a[mid + 1];
break;
}
}
}
a[0] = u;
sizeA = 1;
int32_t v;
low = 0;
high = comps[comp2].size() - 1;
while(low <= high) {
if(low == high) {
v = comps[comp2][low];
break;
}
int32_t mid = (low + high) / 2;
sizeB = 0;
for(int32_t i = low; i <= mid; i++) {
b[sizeB] = comps[comp2][i];
sizeB++;
}
if(Query(sizeA, sizeB, a, b) == 1) {
high = mid - 1;
if(low == mid) {
v = b[low];
break;
}
}
else {
low = mid + 1;
if(mid + 1 == high) {
v = b[mid + 1];
break;
}
}
}
Unite(u, v);
SetRoad(u, v);
}
}
/**
void SetRoad(int32_t a, int32_t b) {
std::cout << "The new road is: " << a << " " << b << '\n';
}
int32_t Query(int32_t sizeA, int32_t sizeB, int32_t *a, int32_t *b) {
std::cout << '\n' << "QUERY" << '\n';
std::cout << "A: ";
for(int32_t i = 0; i < sizeA; i++) {
std::cout << a[i] << " ";
}
std::cout << '\n' << "B: ";
for(int32_t i = 0; i < sizeB; i++) {
std::cout << b[i] << " ";
}
std::cout << '\n';
int32_t res;
std::cin >> res;
return res;
}
int main() {
Run(4);
}
*/
#undef Run run
#undef Query query
#undef int32_t int
Compilation message
icc.cpp:253:12: warning: extra tokens at end of #undef directive
#undef Run run
^~~
icc.cpp:254:14: warning: extra tokens at end of #undef directive
#undef Query query
^~~~~
icc.cpp:255:16: warning: extra tokens at end of #undef directive
#undef int32_t int
^~~
icc.cpp: In function 'void run(int)':
icc.cpp:52:52: warning: unused variable 'aCpy' [-Wunused-variable]
int32_t sizeA, sizeB, a[MAX_N + 5], b[MAX_N + 5], aCpy[MAX_N + 5];
^~~~
icc.cpp:220:10: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
SetRoad(u, v);
^
icc.cpp:220:10: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
424 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
424 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
424 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
552 KB |
Query cities not in range [1, n] |
| 2 |
Halted |
0 ms |
0 KB |
- |
