#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "park.h"
const int MAX_N = 1400;
static int Place[1400];
int n, qcnt;
int mrand(int l, int r) {
static random_device rd;
static mt19937 gen(rd());
return uniform_int_distribution(l, r)(gen);
}
int qry_list(int a, int b, vector<int> go) {
++qcnt;
static int ok[MAX_N];
fill(ok, ok + n, 0);
for (int i : go) ok[i] = true;
ok[a] = ok[b] = true;
if (a > b) swap(a, b);
return Ask(a, b, ok);
}
int qry_tf(int a, int b, vector<int> go) {
++qcnt;
static int ok[MAX_N];
copy(AI(go), ok);
if (a > b) swap(a, b);
return Ask(a, b, ok);
}
void ans(int a, int b) {
if (a > b) swap(a, b);
Answer(a, b);
}
bool on_tree[MAX_N];
vector<int> edge[MAX_N];
vector<int> find_path(int a, int b) {
vector<int> onpath(n);
for (int i = 0;i < n;++i) if (!on_tree[i])
onpath[i] = true;
onpath[a] = onpath[b] = true;
vector<int> allon;
for (int i = 0;i < n;++i) if (i != a && i != b && onpath[i])
allon.pb(i);
function<void(vector<int>)> kick = [&](vector<int> all) {
if (all.empty()) return;
for (int x : all) onpath[x] = false;
if (qry_tf(a, b, onpath)) return;
for (int x : all) onpath[x] = true;
if (all.size() == 1) return;
int mid = all.size() / 2;
vector<int> l(begin(all), begin(all) + mid), r(begin(all) + mid, end(all));
kick(l), kick(r);
};
kick(allon);
// for (int i = 0;i < n;++i) if (i != a && i != b) {
// onpath[i] = false;
// if (!qry_tf(a, b, onpath)) onpath[i] = true;
// }
vector<int> path;
for (int i = 0;i < n;++i) if (i != a && i != b && onpath[i])
path.pb(i);
function<void(int, int)> qst = [&](int l, int r) {
if (r-l+1 <= 1) return;
int p = mrand(l, r);
vector<int> lhs, rhs;
onpath[ path[p] ] = false;
for (int i = l;i <= r;++i) if (i != p) {
if (qry_tf(a, path[i], onpath))
lhs.pb(path[i]);
else
rhs.pb(path[i]);
}
onpath[ path[p] ] = true;
int np = lhs.size();
lhs.pb(path[p]);
lhs.insert(end(lhs), AI(rhs));
for (int i = 0, j = l;i < lhs.size();++i) {
path[j++] = lhs[i];
}
qst(l, l + np-1);
qst(l+np+1, r);
};
qst(0, (int) path.size() - 1);
path.insert(begin(path), a);
path.insert(end(path), b);
return path;
}
void add_edge(int a, int b) {
edge[a].pb(b), edge[b].pb(a);
ans(a, b);
}
void put_in(vector<int> path) {
for (int i = 1;i < path.size();++i)
add_edge(path[i-1], path[i]);
for (int x : path) on_tree[x] = true;
}
bool done[MAX_N];
vector<int> dfs_order(int x, int lst = -1) {
static vector<int> stk;
if (lst == -1) stk.clear();
stk.pb(x);
for (int u : edge[x]) if (u != lst && !done[u]) {
dfs_order(u, x);
}
if (lst == -1) return stk;
return {};
}
void solve_tree() {
put_in({0});
for (int i = 0;i < n;++i) if (!on_tree[i]) {
vector<int> in = dfs_order(0);
vector<int> out;
for (int j = 0;j < n;++j) if (!on_tree[j])
out.pb(j);
int l = 0, r = (int) in.size() - 1, mid;
while (l < r) {
mid = l + r >> 1;
vector<int> ok = out;
ok.insert(end(ok), begin(in), begin(in) + mid + 1);
if (qry_list(0, i, ok))
r = mid;
else l = mid+1;
}
int p = in[l];
put_in(find_path(p, i));
}
}
void find_graph(int x, vector<int> con) {
if (con.empty()) return;
if (qry_list(x, con[0], con) == false) return;
if (con.size() == 1) {
ans(x, con[0]);
return;
}
int mid = con.size() / 2;
vector<int> l(begin(con), begin(con)+mid), r(begin(con)+mid, end(con));
find_graph(x, l), find_graph(x, r);
}
void make_graph() {
vector<int> od = dfs_order(0);
reverse(AI(od)); od.resize(n - 2);
for (int x : od) {
int pa = -1;
for (int u : edge[x]) if (!done[u]) {
assert(pa == -1);
pa = u;
}
assert(pa != -1);
done[pa] = done[x] = true;
vector<int> lft = dfs_order(0);
find_graph(x, lft);
done[pa] = false;
}
}
void Detect(int T, int N) {
n = N;
DE(N, T);
if (T == 1) {
for (int i = 0;i < n;++i)
for (int j = i+1;j < n;++j)
if (qry_list(i, j, {i, j}))
ans(i, j);
return;
}
solve_tree();
if (T == 5) {
make_graph();
}
}
Compilation message
park.cpp: In lambda function:
park.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i = 0, j = l;i < lhs.size();++i) {
| ~~^~~~~~~~~~~~
park.cpp: In function 'void put_in(std::vector<int>)':
park.cpp:126:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int i = 1;i < path.size();++i)
| ~~^~~~~~~~~~~~~
park.cpp: In function 'void solve_tree()':
park.cpp:154:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
154 | mid = l + r >> 1;
| ~~^~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
park.cpp:201:2: note: in expansion of macro 'DE'
201 | DE(N, T);
| ^~
park.cpp: At global scope:
park.cpp:20:12: warning: 'Place' defined but not used [-Wunused-variable]
20 | static int Place[1400];
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
7 ms |
332 KB |
Output is correct |
| 3 |
Correct |
7 ms |
332 KB |
Output is correct |
| 4 |
Correct |
8 ms |
332 KB |
Output is correct |
| 5 |
Correct |
8 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
608 KB |
Output is correct |
| 2 |
Correct |
170 ms |
636 KB |
Output is correct |
| 3 |
Correct |
120 ms |
560 KB |
Output is correct |
| 4 |
Correct |
121 ms |
652 KB |
Output is correct |
| 5 |
Correct |
106 ms |
580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
580 KB |
Output is correct |
| 2 |
Correct |
201 ms |
624 KB |
Output is correct |
| 3 |
Correct |
183 ms |
588 KB |
Output is correct |
| 4 |
Correct |
194 ms |
612 KB |
Output is correct |
| 5 |
Correct |
189 ms |
656 KB |
Output is correct |
| 6 |
Correct |
179 ms |
580 KB |
Output is correct |
| 7 |
Correct |
198 ms |
576 KB |
Output is correct |
| 8 |
Correct |
185 ms |
540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
540 KB |
Output is correct |
| 2 |
Correct |
160 ms |
580 KB |
Output is correct |
| 3 |
Correct |
159 ms |
652 KB |
Output is correct |
| 4 |
Correct |
110 ms |
708 KB |
Output is correct |
| 5 |
Correct |
154 ms |
632 KB |
Output is correct |
| 6 |
Correct |
147 ms |
556 KB |
Output is correct |
| 7 |
Correct |
93 ms |
580 KB |
Output is correct |
| 8 |
Correct |
149 ms |
552 KB |
Output is correct |
| 9 |
Correct |
123 ms |
584 KB |
Output is correct |
| 10 |
Correct |
166 ms |
708 KB |
Output is correct |
| 11 |
Correct |
183 ms |
516 KB |
Output is correct |
| 12 |
Correct |
177 ms |
708 KB |
Output is correct |
| 13 |
Correct |
89 ms |
528 KB |
Output is correct |
| 14 |
Correct |
189 ms |
616 KB |
Output is correct |
| 15 |
Correct |
79 ms |
656 KB |
Output is correct |
| 16 |
Correct |
182 ms |
580 KB |
Output is correct |
| 17 |
Correct |
202 ms |
516 KB |
Output is correct |
| 18 |
Correct |
170 ms |
636 KB |
Output is correct |
| 19 |
Correct |
106 ms |
724 KB |
Output is correct |
| 20 |
Correct |
138 ms |
580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
162 ms |
516 KB |
Wrong Answer[3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
