oj.uz

Submission #125101

# Submission time Handle Problem Language Result Execution time Memory
125101 2019-07-04T15:32:39 Z johutha ICC (CEOI16_icc) C++14
0 / 100
 2 ms 376 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;
}

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 + 1)]) a.push_back(i);
                else b.push_back(i + 1);
            }
            if (query(a.size(), b.size(), a.data(), b.data())) break;
        }
        int first = binsearch(a, b);
        int second = binsearch(b, a);
        setRoad(first, second);
        uf.unite(first, second);
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -