oj.uz

Submission #869553

# Submission time Handle Problem Language Result Execution time Memory
869553 2023-11-04T17:30:25 Z borisAngelov ICC (CEOI16_icc) C++17
90 / 100
 89 ms 856 KB 
#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)
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Ok! 112 queries used.
2 Correct 4 ms 600 KB Ok! 103 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory 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.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory 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.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory 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.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory 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.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 600 KB Too many queries! 1670 out of 1625
2 Halted 0 ms 0 KB -