| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 113729 | MAMBA | ICC (CEOI16_icc) | C++17 | 0 ms | 0 KiB |
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 "icc.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 110;
int sz[N], par[N];
vector<int> vec[N];
set<int> st;
int getPAr(int v) {
if (par[v] == -1) return v;
return getPar(par[v]);
}
inline void merge(int u , int v) {
v = getPar(v);
u = getPar(u);
if (sz[v] > sz[u]) swap(v , u);
for (auto e : h[v])
h[u].pb(e);
h[v].clear();
par[v] = u;
sz[u] += sz[v];
st.erase(v);
}
int a[N], b[N];
unordered_map<int , int> mp , arr;
int ptr;
inline void solve() {
prt = 0;
mp.clear();
arr.clear();
for (auto e : st) {
arr[ptr] = e;
mp[e] = ptr++;
}
int xor_ = 0;
for (int i = 0; (1 << i) <= ptr; i++) {
int size_a = 0;
int size_b = 0;
rep(j , 0 , ptr) {
if ((j >> i) & 1) {
for (auto e : h[arr[j]])
a[size_a++] = e;
}
else {
for (auto e : h[arr[j]])
b[size_b++] = e;
}
}
xor_ |= (query(size_a , size_b , a , b) ? (1 << i) : 0);
}
int now_a = 0, int now_b = 0;
now_b |= 1 << __builtin_ctz(xor_);
for (int i = 0; (1 << i) <= ptr; i++) {
if (b & (1 << i)) continue;
if ((xor_ >> i) & 1) {
int size_a = 0;
int size_b = 0;
rep(j , 0 , ptr) {
int must = ((1 << __builtin_ctz(xor_)) | ((1 << i) - 1));
if (j & must == nowa) {
if ((j >> i) & 1)
for (auto e : h[arr[j]])
a[size_a++] = e;
}
else if (j & must == nowb) {
if ((j >> i) & 1) ;
else
for (auto e: h[arr[j]])
b[size_b++] = e;
}
}
if (query(size_a , size_ , a , b))
now_a += (1 << i);
else
now_b += (1 << i);
}
else {
int size_a = 0;
int size_b = 0;
rep(j , 0 , ptr) {
int must = ((1 << __builtin_ctz(xor_)) | ((1 << i) - 1));
if (j & must == nowa) {
if ((j >> i) & 1)
for (auto e : h[arr[j]])
a[size_a++] = e;
}
else if (j & must == nowb) {
if ((j >> i) & 1)
for (auto e : h[arr[j]])
b[size_b++] = e;
}
}
if (query(size_a , size_ , a , b)) {
now_a += (1 << i);
now_b += (1 << i);
}
}
}
now_a = arr[now_a];
now_b = arr[now_b];
int lo = 0, hi = h[now_a].size();
while (lo != hi - 1) {
int mid = lo + hi >> 1;
int size_a = 0;
int size_b = 0;
rep(i , 0 , mid)
a[size_a++] = h[now_a][i];
for (auto e : h[now_b])
b[size_b++] = e;
if (query(size_a , size_b , a , b))
hi = mid;
else lo = mid;
}
int man = lo;
lo = 0, hi = h[now_b].size();
while (lo != hi - 1) {
int mid = lo + hi >> 1;
a[0] = h[now_a][man];
rep(i , 0 , mid)
b[i] = h[now_b][i];
if (query(1 , mid , a , b));
hi = mid;
else
lo = mid;
}
setRoad(h[now_a][man] , h[now_b][lo]);
merge(h[now_a][man] , h[now_b][lo]);
}
void run(int n) {
rep(i , 1 , n + 1)
st.insert(i);
rep(i , 0 , n)
solve();
}