oj.uz

Submission #442695

# Submission time Handle Problem Language Result Execution time Memory
442695 2021-07-08T16:00:19 Z Lam_lai_cuoc_doi ICC (CEOI16_icc) C++17
100 / 100
 189 ms 484 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 1e2 + 5;
struct dsu
{
    int n;
    int par[N];
    dsu()
    {
        memset(par, -1, sizeof par);
    }
    int findpar(int v)
    {
        return par[v] < 0 ? v : par[v] = findpar(par[v]);
    }
    void Merge(int u, int v)
    {
        u = findpar(u);
        v = findpar(v);
        if (u == v)
            return;
        if (par[u] < par[v])
            swap(u, v);
        par[v] += par[u];
        par[u] = v;
    }
} f;
int a[N], b[N], x, y, c[N];

#include "icc.h"

#define bit(i, x) (((x) >> (i)) & 1)

int Cal(int m, int a[N], int n, int b[N])
{
    int l = 1, r = m;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        for (int i = l; i <= mid; ++i)
            c[i - l] = a[i - 1];

        if (query(mid - l + 1, n, c, b))
            r = mid - 1;
        else
            l = mid + 1;
    }

    return a[l - 1];
}

void run(int n)
{
    f.n = n;
    for (int i = 1; i < n; ++i)
    {
        int XOR(0);
        for (int j = __lg(n); ~j; --j)
        {
            x = 0;
            y = 0;
            for (int t = 1; t <= n; ++t)
                if (bit(j, f.findpar(t)))
                    a[x++] = t;
                else
                    b[y++] = t;
            if (x != 0 && y != 0 && query(x, y, a, b))
                XOR |= 1 << j;
        }
        int v = __lg(XOR & -XOR);

        //cout << v << " ok\n";

        int A(0), B(0);
        B |= 1 << v;

        for (int j = __lg(n); ~j; --j)
            if (j != v)
            {
                x = y = 0;
                if (bit(j, XOR))
                {
                    for (int t = 1; t <= n; ++t)
                        if (!bit(j, f.findpar(t)) && !bit(v, f.findpar(t)))
                            a[x++] = t;
                        else if (bit(j, f.findpar(t)) && bit(v, f.findpar(t)))
                            b[y++] = t;
                    if (x != 0 && y != 0 && query(x, y, a, b))
                        B |= 1 << j;
                    else
                        A |= 1 << j;
                }
                else
                {
                    for (int t = 1; t <= n; ++t)
                        if (!bit(j, f.findpar(t)) && bit(v, f.findpar(t)))
                            a[x++] = t;
                        else if (!bit(j, f.findpar(t)) && !bit(v, f.findpar(t)))
                            b[y++] = t;
                    if (x == 0 || y == 0 || !query(x, y, a, b))
                    {
                        B |= 1 << j;
                        A |= 1 << j;
                    }
                }
            }

        //cout << A << " " << B << "\n";

        x = y = 0;
        for (int t = 1; t <= n; ++t)
            if (f.findpar(t) == A)
                a[x++] = t;
            else if (f.findpar(t) == B)
                b[y++] = t;

        if (x != 1)
        {
            a[0] = Cal(x, a, y, b);
            x = 1;
        }
        if (y != 1)
        {
            b[0] = Cal(y, b, x, a);
            y = 1;
        }
        f.Merge(a[0], b[0]);
        setRoad(a[0], b[0]);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 460 KB Ok! 124 queries used.
2 Correct 7 ms 460 KB Ok! 119 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 460 KB Ok! 749 queries used.
2 Correct 44 ms 472 KB Ok! 610 queries used.
3 Correct 45 ms 460 KB Ok! 653 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 480 KB Ok! 1803 queries used.
2 Correct 138 ms 476 KB Ok! 1467 queries used.
3 Correct 151 ms 480 KB Ok! 1821 queries used.
4 Correct 144 ms 476 KB Ok! 1610 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 484 KB Ok! 1746 queries used.
2 Correct 159 ms 480 KB Ok! 1708 queries used.
3 Correct 141 ms 480 KB Ok! 1572 queries used.
4 Correct 156 ms 472 KB Ok! 1820 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 460 KB Ok! 1570 queries used.
2 Correct 148 ms 472 KB Ok! 1578 queries used.
3 Correct 139 ms 472 KB Ok! 1538 queries used.
4 Correct 189 ms 460 KB Ok! 1611 queries used.
5 Correct 150 ms 480 KB Ok! 1738 queries used.
6 Correct 138 ms 460 KB Ok! 1514 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 476 KB Ok! 1554 queries used.
2 Correct 135 ms 480 KB Ok! 1504 queries used.