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 <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "icc.h"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> using ordset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int MAXN = 110;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
struct union_find {
int par[MAXN];
void init() {
for (int i = 0; i < MAXN; i++) {
par[i] = i;
}
}
int find (int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
void merge (int x, int y) {
par[find(x)] = find(y);
}
} uf;
int N;
int tmpa[MAXN], tmpb[MAXN];
vector<int> verts[MAXN];
int query (vector<int> a, vector<int> b) {
copy(all(a), tmpa);
copy(all(b), tmpb);
return query(a.size(), b.size(), tmpa, tmpb);
}
vector<int> getverts (vector<int> vc) {
vector<int> v;
for (int c : vc) {
v.insert(v.end(), all(verts[c]));
}
return v;
}
int queryc (vector<int> ca, vector<int> cb) {
return query(getverts(ca), getverts(cb));
}
pii findedge() {
#warning reset!
for (int i = 1; i <= N; i++) {
verts[i].clear();
}
vector<int> reps;
for (int i = 1; i <= N; i++) {
verts[uf.find(i)].push_back(i);
if (i == uf.find(i)) {
reps.push_back(i);
}
}
//ok while it is true
//which bit does it differ in?
int xoedge = 0; //xor of edge
int nbt = 7;
for (int bt = 0; bt < 7; bt++) {
//bt = bit that it differs by
vector<int> vca, vcb;
for (int i = 0; i < reps.size(); i++) {
if (i & (1 << bt)) {
vca.push_back(reps[i]);
} else {
vcb.push_back(reps[i]);
}
}
if (!vca.empty() && !vcb.empty()) {
xoedge ^= (queryc(vca, vcb) << bt);
} else {
nbt = bt;
break;
}
}
int bd = __builtin_ctz(xoedge); //bit that is different
int cmpa = 0, cmpb = (1 << bd);
for (int bt = 0; bt < nbt; bt++) {
if (bt == bd) {
continue;
}
vector<int> vca, vcb;
if (xoedge & (1 << bt)) {
//they differ in this bit
for (int i = 0; i < reps.size(); i++) {
int bibt = (i >> bt) & 1; //bit of i that is at position bt
int bibd = (i >> bd) & 1; //bit of i that is at position bd
if (bibt == 0 && bibd == 0) {
vca.push_back(reps[i]);
} else if (bibt == 1 && bibd == 1) {
vcb.push_back(reps[i]);
}
}
if (queryc(vca, vcb)) {
//then yes. cmpa has this bit as 0, cmpb has this bit as 1.
cmpb ^= (1 << bt);
} else {
cmpa ^= (1 << bt);
}
} else {
//they are same in this bit. is it zero or one?
for (int i = 0; i < reps.size(); i++) {
int bibt = (i >> bt) & 1; //bit of i that is at position bt
int bibd = (i >> bd) & 1; //bit of i that is at position bd
if (bibt == 0) {
if (bibd == 0) {
vca.push_back(reps[i]);
} else {
vcb.push_back(reps[i]);
}
}
}
if (queryc(vca, vcb)) {
//"bt" is zero
} else {
//"bt" is one
cmpa ^= (1 << bt);
cmpb ^= (1 << bt);
}
}
}
vector<int> va = verts[reps[cmpa]], vb = verts[reps[cmpb]];;
while (va.size() > 1) {
int half = va.size() / 2;
if (query(vector<int> (va.begin(), va.begin() + half), vb)) {
va.resize(half);
} else {
va.erase(va.begin(), va.begin() + half);
}
}
while (vb.size() > 1) {
int half = vb.size() / 2;
if (query(va, vector<int> (vb.begin(), vb.begin() + half))) {
vb.resize(half);
} else {
vb.erase(vb.begin(), vb.begin() + half);
}
}
//ok now we have the components
//get down to vertices
return pii(va[0], vb[0]);
}
void run (int nnnnn) {
N = nnnnn;
uf.init();
//just randomize it lol
for (int i = 0; i < N - 1; i++) {
pii p = findedge();
setRoad(p.fi, p.se);
uf.merge(p.fi, p.se);
}
}
Compilation message (stderr)
icc.cpp:62:2: warning: #warning reset! [-Wcpp]
#warning reset!
^~~~~~~
icc.cpp: In function 'pii findedge()':
icc.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < reps.size(); i++) {
~~^~~~~~~~~~~~~
icc.cpp:107:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < reps.size(); i++) {
~~^~~~~~~~~~~~~
icc.cpp:125:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < reps.size(); i++) {
~~^~~~~~~~~~~~~
# | 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... |