#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double;
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(0x1557);
template<class> struct is_container : false_type {};
template<class... Ts> struct is_container<vector<Ts...>> : true_type {};
template<class... Ts> struct is_container<map<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_map<Ts...>> : true_type {};
template<class... Ts> struct is_container<set<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_set<Ts...>> : true_type {};
template<class... Ts> struct is_container<multiset<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_multiset<Ts...>> : true_type {};
template<class T, class = typename enable_if<is_container<T>::value>::type>
ostream& operator<<(ostream &o, T x) {
#ifndef TAMREF
return o;
#endif
int f = 1;
o << "{";
for (auto y : x) {
o << (f ? "" : ", ") << y;
f = 0;
}
return o << "}";
}
template<class T, class U>
ostream& operator<<(ostream &o, pair<T, U> x) {
#ifndef TAMREF
return o;
#endif
return o << "(" << x.first << ", " << x.second << ")";
}
void Solve(int);
#ifdef TAMREF
namespace {
const int MAX_N = 2000;
const int MAX_CALLS = 100000;
void WrongAnswer(int code) {
printf("Wrong Answer [%d]\n", code);
exit(0);
}
int N, num_calls;
std::vector<int> graph[MAX_N];
std::set<std::pair<int, int>> edges, edges_reported;
int weight[MAX_N];
bool Visit(int p, int e, int rt = -1) {
if (p == e) {
++weight[p];
return true;
}
for (int q : graph[p]) {
if (q != rt) {
if (Visit(q, e, p)) {
++weight[p];
return true;
}
}
}
return false;
}
} // namespace
int Query(int u, int v, int w, bool stealth=false) {
if(stealth) --num_calls;
if(!stealth) {
debug("Q(%d %d %d) = ", u, v, w);
}
if (!(0 <= u && u <= N - 1 && 0 <= v && v <= N - 1 && 0 <= w && w <= N - 1 &&
u != v && u != w && v != w)) {
WrongAnswer(1);
}
if (++num_calls > MAX_CALLS) {
WrongAnswer(2);
}
std::fill(weight, weight + N, 0);
Visit(u, v);
Visit(u, w);
Visit(v, w);
for (int x = 0; x < N; ++x) {
if (weight[x] == 3) {
if(!stealth) debug("%d\n", x);
return x;
}
}
printf("Error: the input may be invalid\n");
exit(0);
}
void Bridge(int u, int v) {
debug("B(%d %d)\n", u, v);
if (!(0 <= u && u < v && v <= N - 1)) {
WrongAnswer(3);
}
if (!(edges.count(std::make_pair(u, v)) >= 1)) {
WrongAnswer(4);
}
if (!(edges_reported.count(std::make_pair(u, v)) == 0)) {
WrongAnswer(5);
}
edges_reported.insert(std::make_pair(u, v));
}
int main() {
if (scanf("%d", &N) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
for (int i = 0; i < N - 1; ++i) {
int u, v;
if (scanf("%d%d", &u, &v) != 2) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
graph[u].push_back(v);
graph[v].push_back(u);
edges.insert(std::make_pair(u, v));
}
num_calls = 0;
Solve(N);
if (edges_reported.size() != static_cast<size_t>(N - 1)) {
WrongAnswer(6);
}
printf("Accepted: %d\n", num_calls);
return 0;
}
#endif
void _Query(int a, int b, int c, int expt) {
#ifdef TAMREF
assert(Query(a, b, c, true) == expt);
#endif
}
void _Bridge(int x, int y) {
if(x < y) Bridge(x, y);
else Bridge(y, x);
}
void solve(vector<int> v) {
int n = szz(v);
vector<bool> vis(n);
vector<vector<int>> ch(n);
vector<int> sz(n), par(n), chain_head(n), chain_leaf(n);
fill(all(par), -1);
iota(all(chain_head), 0);
iota(all(chain_leaf), 0);
int r = Query(v[0], v[1], v[2]);
auto manage_hld = [&](int p) {
for(int g = par[p]; g != -1; p = g, g = par[g]) {
sz[g] += 1;
int k = find(all(ch[g]), p) - ch[g].begin();
for(int j = k; j && sz[ch[g][j-1]] < sz[ch[g][j]]; j--) swap(ch[g][j-1], ch[g][j]);
if(k && ch[g][0] == p) { // change head and heavy chain
debug("%d became a new heavy chain of %d, beating %d\n", p, g, ch[g][1]);
int q = ch[g][1];
chain_leaf[q] = chain_leaf[chain_head[g]];
chain_leaf[chain_head[g]] = chain_leaf[p];
for(int i = q; i != -1; i = szz(ch[i]) ? ch[i][0] : -1) chain_head[i] = q;
for(int i = p; i != -1; i = szz(ch[i]) ? ch[i][0] : -1) chain_head[i] = chain_head[g];
}
}
};
auto append_as_leaf = [&](int p, int x) {
assert(!vis[x]);
vis[x] = 1;
par[x] = p;
ch[p].pp(x);
sz[x] = 1;
sz[p] += 1;
if(szz(ch[p]) == 1) {
chain_head[x] = chain_head[p];
chain_leaf[ chain_head[x] ] = x;
} else {
chain_head[x] = chain_leaf[x] = x;
}
// maintain HLD structure
manage_hld(p);
};
vis[r] = 1;
for(int i = 0; i < 3; i++) {
if(!vis[v[i]]) append_as_leaf(r, v[i]);
}
auto splice_path = [&](int p, int l, int m) {
assert(par[l] == p);
sz[m] = sz[l] + 1;
par[l] = m;
ch[m].pp(l);
chain_head[m] = (chain_head[l] == l ? m : chain_head[l]);
if(l == chain_head[l]) chain_leaf[m] = chain_leaf[l];
for(int i = l; i != -1; i = szz(ch[i]) ? ch[i][0] : -1) chain_head[i] = chain_head[m];
par[m] = p;
auto it = find(all(ch[p]), l);
assert(it != ch[p].end());
*it = m;
manage_hld(m);
};
auto bisect_on_path = [&](int u, int v, int x) {
assert(!vis[x]);
vis[x] = 1;
// generate joint path in O(n)
vector<int> pu, pv;
for(int x = u; x != -1; x = par[x]) pu.pp(x);
for(int x = v; x != -1; x = par[x]) pv.pp(x);
int lc = -1, z = min(szz(pu), szz(pv));
for(int i = 0; i < z; i++) {
if(pu.back() == pv.back()) {
lc = pu.back();
pu.pop_back(); pv.pop_back();
}
}
assert(lc != -1);
pu.pp(lc);
copy(pv.rbegin(), pv.rend(), back_inserter(pu));
// binary search to insert x
int lo = 0, hi = szz(pu) - 2, mi;
while(lo < hi) {
mi = (lo + hi + 1) >> 1;
int q = Query(x, pu[mi], v);
assert(q == x || q == pu[mi]);
if(q == pu[mi]) hi = mi - 1;
else lo = mi;
}
// hi should be answer
_Query(pu[hi], pu[hi+1], x, x);
if(par[pu[hi]] == pu[hi + 1]) {
splice_path(pu[hi+1], pu[hi], x);
} else {
splice_path(pu[hi], pu[hi+1], x);
}
};
auto single_branch = [&](int p, int l, int x, bool last_branch) -> int {
int y = Query(p, l, x);
if(y == p) {
if(last_branch) {
append_as_leaf(p, x);
return -1;
} else {
return p;
}
}
if(y == l) { // subtree of leaf
append_as_leaf(l, x);
return -1;
}
if(y == x) {
bisect_on_path(p, l, x);
return -1;
}
if(vis[y]) return y;
bisect_on_path(p, l, y);
append_as_leaf(y, x);
return -1;
};
auto double_branch = [&](int rt1, int rt2, int x, bool last_branch) -> int {
int l1 = chain_leaf[chain_head[rt1]], l2 = chain_leaf[chain_head[rt2]];
int y = Query(l1, l2, x);
if(y == l1 || y == l2) {
append_as_leaf(y, x);
return -1;
}
if(y == par[rt1]) {
if(last_branch) {
append_as_leaf(y, x);
return -1;
}
return y;
}
if(y == x) {
bisect_on_path(l1, l2, x);
return -1;
}
if(vis[y]) return y;
bisect_on_path(l1, l2, y);
append_as_leaf(y, x);
return -1;
};
for(int i = 3; i < n; i++) {
int x = v[i];
debug("processing %d\n", x);
if(vis[x]) continue;
for(int p = r; p != -1 && sz[p] > 1;) {
debug("x = %d, p = %d\n", x, p);
if(szz(ch[p]) == 1) {
debug("bough\n");
p = single_branch(p, chain_leaf[chain_head[p]], x, true);
} else {
for(int j = 0, init_p = p; p == init_p && j < szz(ch[p]); j += 2) {
if(j + 1 == szz(ch[p])) {
p = single_branch(p, chain_leaf[ch[p][j]], x, true);
} else {
debug("double branch\n");
p = double_branch(ch[p][j], ch[p][j+1], x, j + 2 == szz(ch[p]));
debug("double branch done. p = %d\n", p);
}
}
}
}
debug("par[%d] = %d\n", x, par[x]);
}
for(int i = 0; i < n; i++) {
if(par[i] != -1) _Bridge(i, par[i]);
}
}
void Solve(int n) {
vector<int> v(n);
iota(all(v), 0);
shuffle(all(v), rng);
solve(v);
}
Compilation message
meetings.cpp: In function 'void _Bridge(int, int)':
meetings.cpp:172:13: error: 'Bridge' was not declared in this scope
172 | if(x < y) Bridge(x, y);
| ^~~~~~
meetings.cpp:173:8: error: 'Bridge' was not declared in this scope
173 | else Bridge(y, x);
| ^~~~~~
meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:185:11: error: 'Query' was not declared in this scope
185 | int r = Query(v[0], v[1], v[2]);
| ^~~~~
meetings.cpp: In lambda function:
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
meetings.cpp:193:9: note: in expansion of macro 'debug'
193 | debug("%d became a new heavy chain of %d, beating %d\n", p, g, ch[g][1]);
| ^~~~~
meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
meetings.cpp:331:5: note: in expansion of macro 'debug'
331 | debug("processing %d\n", x);
| ^~~~~
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
meetings.cpp:335:7: note: in expansion of macro 'debug'
335 | debug("x = %d, p = %d\n", x, p);
| ^~~~~
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
meetings.cpp:337:9: note: in expansion of macro 'debug'
337 | debug("bough\n");
| ^~~~~
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
meetings.cpp:344:13: note: in expansion of macro 'debug'
344 | debug("double branch\n");
| ^~~~~
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
meetings.cpp:346:13: note: in expansion of macro 'debug'
346 | debug("double branch done. p = %d\n", p);
| ^~~~~
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
meetings.cpp:351:5: note: in expansion of macro 'debug'
351 | debug("par[%d] = %d\n", x, par[x]);
| ^~~~~
