Submission #869553

#	Time	Username	Problem	Language	Result	Execution time	Memory
869553		borisAngelov	ICC (CEOI16_icc)	C++17	90 / 100	89 ms	856 KiB

icc

#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 (stderr)

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)
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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