This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)]) a.push_back(i + 1);
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);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |