| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 856500 | Nhoksocqt1 | 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;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 102;
vector<int> adj[MAXN], B[MAXN];
int a[MAXN], b[MAXN], lt[MAXN], numNode;
bool answer[MAXN];
void dfs(int u) {
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it]);
if(lt[v] < 0) {
lt[v] = lt[u];
dfs(v);
}
}
}
#ifdef Nhoksocqt1
vector<int> jAdj[MAXN];
vector<ii> jury_edges;
int juryLT[MAXN], cntJury(0);
bool jury_hase[MAXN][MAXN];
void jury_dfs(int u) {
for (int it = 0; it < sz(jAdj[u]); ++it) {
int v(jAdj[u][it]);
if(!juryLT[v]) {
juryLT[v] = juryLT[u];
jury_dfs(v);
}
}
}
void addRoad(void) {
if(cntJury >= numNode)
return;
int u(jury_edges[cntJury].fi), v(jury_edges[cntJury].se);
jAdj[u].push_back(v);
jAdj[v].push_back(u);
jury_hase[u][v] = jury_hase[v][u] = 1;
for (int i = 1; i <= numNode; ++i)
juryLT[i] = 0;
int cntNow(0);
for (int i = 1; i <= numNode; ++i) {
if(!juryLT[i]) {
juryLT[i] = ++cntNow;
jury_dfs(i);
}
}
}
void setRoad(int u, int v) {
if(u > v)
swap(u, v);
assert(u == jury_edges[cntJury].fi && v == jury_edges[cntJury].se);
++cntJury;
addRoad();
}
int query(int na, int nb, int a[], int b[]) {
/*cout << "QUERY FOR :\n" << na << ' ';
for (int it = 0; it < na; ++it) cout << a[it] << ' '; cout << '\n' << nb << ' ';
for (int it = 0; it < nb; ++it) cout << b[it] << ' '; cout << '\n';*/
for (int i = 0; i < na; ++i) {
for (int j = 0; j < nb; ++j) {
if(jury_hase[min(a[i], b[j])][max(a[i], b[j])])
return 1;
}
}
return 0;
}
#endif // Nhoksocqt1
void run(int _N) {
/*int res(0);
for (int i = 1; i < 100; ++i) {
int x = 31 - __builtin_clz(i + 1) + (__builtin_popcount(i + 1) > 1);
res += 2 * x - 1;
int y = 31 - __builtin_clz(i / 2 + 1) + (__builtin_popcount(i / 2 + 1) > 1);
int z = 31 - __builtin_clz((i + 1) / 2 + 1) + (__builtin_popcount((i + 1) / 2 + 1) > 1);
res += y + z;
cout << 2 * x - 1 << ' ' << y << ' ' << z << '\n';
}
cout << '.' << res << '\n';
return;*/
numNode = _N;
for (int i = 1; i < numNode; ++i) {
for (int j = 0; j <= numNode; ++j)
lt[j] = -1, B[j].clear();
int cnt(0);
for (int j = 1; j <= numNode; ++j) {
if(lt[j] < 0) {
lt[j] = cnt++;
dfs(j);
}
B[lt[j]].push_back(j);
}
int I(0), J(0), maskd(0), log(0);
while((1 << log) < cnt)
++log;
for (int i = log - 1; i >= 0; --i) {
int na(0), nb(0);
for (int j = 0; j < cnt; ++j) {
for (int it = 0; it < sz(B[j]); ++it) {
int u(B[j][it]);
if(j >> i & 1) {
a[na++] = u;
} else {
b[nb++] = u;
}
}
}
answer[i] = query(na, nb, a, b);
//cout << answer[i] << '\n';
}
for (int i = log - 1; i >= 0; --i) {
if(!answer[i])
continue;
maskd |= (1 << i);
if(!J) {
J ^= (1 << i);
continue;
}
I ^= (1 << i);
int na(0), nb(0);
for (int j = 0; j < cnt; ++j) {
if((I & maskd) != (j & maskd) && (J & maskd) != (j & maskd))
continue;
for (int it = 0; it < sz(B[j]); ++it) {
int u(B[j][it]);
if((I & maskd) == (j & maskd)) {
a[na++] = u;
} else {
b[nb++] = u;
}
}
}
int ansNow = (!na || !nb) ? 0 : query(na, nb, a, b);
if(!ansNow) {
I ^= (1 << i);
J ^= (1 << i);
}
}
//cout << I << ' ' << J << '\n';
for (int i = log - 1; i >= 0; --i) {
if(answer[i])
continue;
maskd |= (1 << i);
int na(0), nb(0);
for (int j = 0; j < cnt; ++j) {
if((I & maskd) != (j & maskd) && (J & maskd) != (j & maskd))
continue;
for (int it = 0; it < sz(B[j]); ++it) {
int u(B[j][it]);
if((I & maskd) == (j & maskd)) {
a[na++] = u;
} else {
b[nb++] = u;
}
}
}
int ansNow = (!na || !nb) ? 0 : query(na, nb, a, b);
if(!ansNow) {
I ^= (1 << i);
J ^= (1 << i);
}
}
int na(0), nb(0), K(0), L(0);
for (int it = 0; it < sz(B[J]); ++it)
b[nb++] = B[J][it];
log = 0;
while((1 << log) < sz(B[I]))
++log;
maskd = 0;
for (int j = 0; j < log; ++j) {
na = 0;
K ^= (1 << j);
maskd |= (1 << j);
for (int it = 0; it < sz(B[I]); ++it) {
if((it & maskd) == (K & maskd))
a[na++] = B[I][it];
}
bool ansNow = query(na, nb, a, b);
if(!ansNow)
K ^= (1 << j);
}
log = maskd = 0;
while((1 << log) < sz(B[J]))
++log;
na = 1;
a[0] = B[I][K];
for (int j = 0; j < log; ++j) {
nb = 0;
L ^= (1 << j);
maskd |= (1 << j);
for (int it = 0; it < sz(B[J]); ++it) {
if((it & maskd) == (L & maskd))
b[nb++] = B[J][it];
}
bool ansNow = query(na, nb, a, b);
if(!ansNow)
L ^= (1 << j);
}
//cout << "NEW ROADS: " << B[I][K] << ' ' << B[J][L] << '\n';
setRoad(B[I][K], B[J][L]);
adj[B[I][K]].push_back(B[J][L]);
adj[B[J][L]].push_back(B[I][K]);
}
}