/**
* [S1-3] Well, it's not that difficult to come up with a solution for [S3]. Here,
* we have 1 query for each edge. We iterate through every node u, and let E(u)
* be the set of edges incident to u. We find an arbitrary spanning forest with
* the remaining edges. Assuming that the forest is in fact a tree, then we can
* iterate through every edge of E(u), adding it to the pre-built forest/tree.
* It's easy to see that every time a spanning tree of the whole graph is
* obtained, which means we can determine what edges of E(u) are actually in
* the hidden tree.
* Finally, the pre-built forest may not be a tree, so a bit more work is
* needed. Unfortunately, I have also written a quite ugly piece of impl.
* [S4] Ask E(u), then the result would be deg(u). After noticing this, I realized
* we can determine by tree starting from its leaves. As a leaf only has 1
* neighbour, we can use binary search to find that neighbour. Iteratively
* finding all such edges is a possible solution.
*
* Steps needed: n^2 / 2 for general graphs, 2n * log_2(n) for complete graphs
* Implementation 1 (Solves [S1-3] (bound nearly tight), [S4])
*/
#include <bits/stdc++.h>
#include "simurgh.h"
typedef std::vector<int> vec;
// A disjoint set union structure which supports assigning an int value to each set.
struct DSU {
int n;
vec parent, size, values;
DSU(int _n) {
n = _n;
parent.resize(n);
size.resize(n);
values.assign(n, -1);
for (int k = 0; k < n; k++)
parent[k] = k, size[k] = 1;
}
inline int find(int k) {
if (parent[k] == k)
return k;
return parent[k] = find(parent[k]);
}
bool merge(int a, int b) {
a = find(a), b = find(b);
if (a == b)
return false;
if (size[b] > size[a])
std::swap(a, b);
parent[b] = a, size[a] += size[b];
return true;
}
inline void set_val(int k, int value) { values[find(k)] = value; }
inline int get_val(int k) { return values[find(k)]; }
};
vec square(int n, int m, const std::vector<vec>& graph) {
vec is_ans(m, -1); // -1: unknown
for (int c = 0; c < n; c++) {
DSU dsu(n); // #value_of_set = #pos_of_repr_in_ask[]
int deg = 0;
vec ask;
for (int neighb1 = 0; neighb1 < n; neighb1++) {
if (neighb1 == c)
continue;
deg++;
for (int neighb2 = 0; neighb2 < n; neighb2++) {
if (neighb2 == c || graph[neighb1][neighb2] == -1)
continue;
if (dsu.merge(neighb1, neighb2))
ask.push_back(graph[neighb1][neighb2]);
}
}
for (int neighb = 0; neighb < n; neighb++) {
if (graph[c][neighb] != -1 && dsu.get_val(neighb) == -1) {
dsu.set_val(neighb, ask.size());
ask.push_back(graph[c][neighb]);
}
}
assert(int(ask.size()) == n - 1);
for (int neighb = 0; neighb < n; neighb++) {
if (graph[c][neighb] == -1)
continue;
int& base = is_ans[ask[dsu.get_val(neighb)]];
base = (base == -1 ? 1 : base);
}
int base_num = count_common_roads(ask);
vec result(deg); // Results from count_common_roads()
for (int neighb = 0, l = 0; neighb < n; neighb++) {
int edge_idx = graph[neighb][c];
if (edge_idx == -1)
continue;
if (is_ans[edge_idx] != -1)
continue;
int pos = dsu.get_val(neighb), original = ask[pos];
ask[pos] = edge_idx;
int switched_num = count_common_roads(ask);
result[l++] = switched_num;
if (switched_num > base_num)
is_ans[edge_idx] = 1, is_ans[original] = 0;
ask[pos] = original;
}
for (int neighb = 0, l = 0; neighb < n; neighb++) {
int idx = graph[neighb][c];
if (idx == -1)
continue;
if (is_ans[idx] != -1)
continue;
int rep = ask[dsu.get_val(neighb)];
is_ans[idx] = (result[l++] != base_num ? 1 - is_ans[rep] : is_ans[rep]);
}
}
vec ans;
for (int k = 0; k < m; k++) {
assert(is_ans[k] != -1);
if (is_ans[k] == 1)
ans.push_back(k);
}
assert(int(ans.size()) == n - 1);
return ans;
}
vec complete(int n, const std::vector<vec>& graph) {
vec deg(n, 0);
std::queue<int> leaves;
for (int k = 0; k < n; k++) {
vec ask;
for (int neighb = 0; neighb < n; neighb++) {
if (neighb != k)
ask.push_back(graph[neighb][k]);
}
deg[k] = count_common_roads(ask);
if (deg[k] == 1)
leaves.push(k);
}
vec ans;
std::vector<bool> active(n, true);
while (!leaves.empty() && int(ans.size()) < n - 1) {
int l = leaves.front();
leaves.pop();
active[l] = false;
vec remains;
for (int k = 0; k < n; k++) {
if (active[k])
remains.push_back(k);
}
int a = 0, b = remains.size() - 1;
while (a < b) {
vec ask1 = ans;
int half = (b - a + 1) / 2;
for (int k = a; k < a + half; k++)
ask1.push_back(graph[remains[k]][remains[k + half]]);
if (a % 2 == b % 2)
ask1.push_back(graph[remains.front()][remains.back()]);
vec ask2 = ask1;
for (int k = a; k < a + half; k++) {
ask1.push_back(graph[remains[k]][l]);
ask2.push_back(graph[remains[k + half]][l]);
}
int r1 = count_common_roads(ask1), r2 = count_common_roads(ask2);
if (r1 > r2)
b = a + half - 1;
else if (r1 < r2)
a = a + half;
else
a = b;
}
int neighb = remains[a];
ans.push_back(graph[l][neighb]);
deg[neighb]--;
if (deg[neighb] == 1)
leaves.push(neighb);
}
assert(int(ans.size()) == n - 1);
return ans;
}
vec find_roads(int n, vec u, vec v) {
int m = u.size();
std::vector<vec> graph(n, vec(n, -1));
for (int k = 0; k < m; k++)
graph[u[k]][v[k]] = graph[v[k]][u[k]] = k;
if (m == n * (n - 1) / 2)
return complete(n, graph);
else
return square(n, m, graph);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Incorrect |
0 ms |
304 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
