#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
const int maxn = 105;
int n;
int szA = 0, szB = 0;
int a[maxn];
int b[maxn];
int szC = 0, szD = 0;
int c[maxn];
int d[maxn];
struct DSU
{
int par[maxn];
int sz[maxn];
vector<int> components[maxn];
void build(int n)
{
for (int i = 1; i <= n; ++i)
{
components[i].push_back(i);
par[i] = i;
sz[i] = 1;
}
}
int root(int node)
{
if (node == par[node])
{
return node;
}
return par[node] = root(par[node]);
}
void connect(int x, int y)
{
x = root(x);
y = root(y);
if (x == y)
{
return;
}
if (sz[x] < sz[y])
{
par[x] = y;
sz[y] += sz[x];
for (int i = 0; i < components[x].size(); ++i)
{
components[y].push_back(components[x][i]);
}
}
else
{
par[y] = x;
sz[x] += sz[y];
for (int i = 0; i < components[y].size(); ++i)
{
components[x].push_back(components[y][i]);
}
}
}
};
DSU dsu;
vector<int> componentRoots;
int maxRootNumber = 0;
mt19937 mt(69420);
void run(int n_)
{
srand(time(NULL));
n = n_;
dsu.build(n);
for (int step = 1; step <= n - 1; ++step)
{
componentRoots.clear();
maxRootNumber = 0;
for (int i = 1; i <= n; ++i)
{
if (i == dsu.root(i))
{
componentRoots.push_back(i);
maxRootNumber = max(maxRootNumber, i);
}
}
int maxBitIndex = 0;
while ((1 << (maxBitIndex + 1)) <= maxRootNumber)
{
++maxBitIndex;
}
vector<int> testByBits;
for (int bit = 0; bit <= maxBitIndex; ++bit)
{
testByBits.push_back(bit);
}
shuffle(testByBits.begin(), testByBits.end(), mt);
for (int idx = 0; idx < testByBits.size(); ++idx)
{
int bit = testByBits[idx];
szA = 0;
szB = 0;
for (int i = 0; i < componentRoots.size(); ++i)
{
if ((componentRoots[i] & (1 << bit)) == 0)
{
for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
{
a[szA++] = dsu.components[componentRoots[i]][j];
}
}
else
{
for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
{
b[szB++] = dsu.components[componentRoots[i]][j];
}
}
}
if (szA == 0 || szB == 0)
{
continue;
}
if (idx == testByBits.size() - 1)
{
break;
}
if (query(szA, szB, a, b) == true)
{
break;
}
}
int edgeX = 0;
int edgeY = 0;
int l1 = -1;
int r1 = szA;
while (r1 - l1 > 1)
{
int mid = (l1 + r1) / 2;
szC = 0;
for (int i = 0; i <= mid; ++i)
{
c[szC++] = a[i];
}
if (query(szC, szB, c, b) == true)
{
r1 = mid;
}
else
{
l1 = mid;
}
}
edgeX = a[r1];
szC = 1;
c[0] = edgeX;
int l2 = -1;
int r2 = szB;
while (r2 - l2 > 1)
{
int mid = (l2 + r2) / 2;
szD = 0;
for (int i = 0; i <= mid; ++i)
{
d[szD++] = b[i];
}
if (query(szC, szD, c, d) == true)
{
r2 = mid;
}
else
{
l2 = mid;
}
}
edgeY = b[r2];
dsu.connect(edgeX, edgeY);
setRoad(edgeX, edgeY);
}
}
Compilation message
icc.cpp: In member function 'void DSU::connect(int, int)':
icc.cpp:59:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < components[x].size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~
icc.cpp:69:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < components[y].size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:122:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int idx = 0; idx < testByBits.size(); ++idx)
| ~~~~^~~~~~~~~~~~~~~~~~~
icc.cpp:129:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int i = 0; i < componentRoots.size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:133:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:140:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:152:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | if (idx == testByBits.size() - 1)
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
600 KB |
Ok! 112 queries used. |
| 2 |
Correct |
4 ms |
600 KB |
Ok! 103 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
604 KB |
Ok! 556 queries used. |
| 2 |
Correct |
29 ms |
640 KB |
Ok! 692 queries used. |
| 3 |
Correct |
27 ms |
604 KB |
Ok! 685 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
74 ms |
856 KB |
Ok! 1432 queries used. |
| 2 |
Correct |
85 ms |
624 KB |
Ok! 1713 queries used. |
| 3 |
Correct |
73 ms |
628 KB |
Ok! 1503 queries used. |
| 4 |
Correct |
77 ms |
604 KB |
Ok! 1564 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
74 ms |
624 KB |
Ok! 1472 queries used. |
| 2 |
Correct |
72 ms |
600 KB |
Ok! 1465 queries used. |
| 3 |
Correct |
81 ms |
604 KB |
Ok! 1624 queries used. |
| 4 |
Correct |
71 ms |
600 KB |
Ok! 1461 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
81 ms |
620 KB |
Ok! 1625 queries used. |
| 2 |
Correct |
84 ms |
620 KB |
Ok! 1681 queries used. |
| 3 |
Correct |
84 ms |
604 KB |
Ok! 1674 queries used. |
| 4 |
Correct |
80 ms |
600 KB |
Ok! 1619 queries used. |
| 5 |
Correct |
85 ms |
620 KB |
Ok! 1493 queries used. |
| 6 |
Correct |
89 ms |
848 KB |
Ok! 1635 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
83 ms |
600 KB |
Too many queries! 1670 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
