oj.uz

Submission #125108

# Submission time Handle Problem Language Result Execution time Memory
125108 2019-07-04T15:47:11 Z johutha ICC (CEOI16_icc) C++14
90 / 100
 168 ms 632 KB 
#include <vector>
#include <iostream>
#include "icc.h"
#include <set>
#include <algorithm>

using namespace std;

int log2(int n)
{
    return 32 - __builtin_clz(n) - 1;
}

int _query(int sa, int sb, int a[], int b[])
{
    vector<int> na;
    vector<int> nb;

    for (int i = 0; i < sa; i++)
    {
        na.push_back(a[i] + 1);
    }
    for (int i = 0; i < sb; i++)
    {
        nb.push_back(b[i] + 1);
    }
    return query(sa, sb, na.data(), nb.data());
}

struct unionfind
{
    vector<int> chef;

    int find(int x)
    {
        if(chef[x] == x) return x;
        return chef[x] = find(chef[x]);
    }

    void unite(int a, int b)
    {
        if (rand() & 1) chef[find(a)] = find(b);
        else chef[find(b)] = find(a);
    }

    void init(int n)
    {
        chef.resize(n);
        for(int i = 0; i < n; i++) chef[i] = i;
    }
};

int binsearch(vector<int> &tosearch, vector<int> &other)
{
    int n = tosearch.size();

    int l2 = log2(n) + 1;

    int p = 0;

    for (int i = 0; i < l2; i++)
    {
        vector<int> search;
        for (int j = 0; j < n; j++)
        {
            if ((1<<i) & j) search.push_back(tosearch[j]);
        }
        p += (1<<i)*_query(search.size(), other.size(), search.data(), other.data());
    }
    return tosearch[p];
}

void run(int n)
{
    unionfind uf;
    uf.init(n);
    srand(852935);

    for (int z = 0; z < n - 1; z++)
    {
        set<int> c;
        for (int i = 0; i < n; i++)
        {
            c.insert(uf.find(i));
        }
        vector<int> components;
        for (int i : c)
        {
            components.push_back(i);
        }
        int cs = components.size();

        vector<int> compind(n);
        for (int i = 0; i < cs; i++)
        {
            compind[components[i]] = i;
        }
        int l2 = log2(cs) + 1;
        vector<int> a;
        vector<int> b;

        for (int cl = 0; cl < l2; cl++)
        {
            a.clear();
            b.clear();
            for (int i = 0; i < n; i++)
            {
                if ((1<<cl) & compind[uf.find(i)]) a.push_back(i);
                else b.push_back(i);
            }
            if (_query(a.size(), b.size(), a.data(), b.data())) break;
        }
        int first = binsearch(a, b);
        int second = binsearch(b, a);
        setRoad(first + 1, second + 1);
        uf.unite(first, second);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 104 queries used.
2 Correct 9 ms 504 KB Ok! 116 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 588 KB Ok! 572 queries used.
2 Correct 52 ms 504 KB Ok! 705 queries used.
3 Correct 51 ms 508 KB Ok! 693 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 504 KB Ok! 1536 queries used.
2 Correct 164 ms 572 KB Ok! 1705 queries used.
3 Correct 160 ms 520 KB Ok! 1686 queries used.
4 Correct 156 ms 504 KB Ok! 1616 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 564 KB Ok! 1629 queries used.
2 Correct 160 ms 568 KB Ok! 1665 queries used.
3 Correct 162 ms 572 KB Ok! 1692 queries used.
4 Correct 153 ms 504 KB Ok! 1562 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 632 KB Ok! 1726 queries used.
2 Correct 159 ms 580 KB Ok! 1689 queries used.
3 Correct 162 ms 504 KB Ok! 1699 queries used.
4 Correct 164 ms 572 KB Ok! 1678 queries used.
5 Correct 155 ms 632 KB Ok! 1563 queries used.
6 Correct 161 ms 564 KB Ok! 1627 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 572 KB Too many queries! 1692 out of 1625
2 Halted 0 ms 0 KB -