# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
442671 | Lam_lai_cuoc_doi | ICC (CEOI16_icc) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
constexpr bool typetest = 1;
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;
#include "icc.h"
#define bit(i, x) (((x) >> (i)) & 1)
int Cal(vector<int> &a, vector<int> &b)
{
int l = 1, r = a.size();
while (l <= r)
{
int mid = (l + r) / 2;
vector<int> c(mid - l + 1);
for (int i = l; i <= mid; ++i)
c[i - l] = a[l - 1];
if (query(c.size(), b.size(), c, b))
r = mid - 1;
else
l = mid + 1;
}
return l;
}
void run(int n)
{
f.n = n;
for (int i = 1; i < n; ++i)
{
vector<int> a, b;
for (int j = 6; ~j; --j)
{
a.clear();
for (int t = 1; t <= n; ++t)
if (bit(j, f.findpar(t)))
a.emplace_back(t);
else
b.emplace_back(t);
if (x != 0 && y != 0 && query(a.size(), b.size(), a, b))
break;
}
if ((int)a.size() != 1)
{
a[0] = Cal(a, b);
x = 1;
}
if ((int)b.size() != 1)
{
b[0] = Cal(b, a);
y = 1;
}
f.Merge(a[0], b[0]);
setRoad(a[0], b[0]);
}
}