#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cassert>
#include <iomanip>
#include <cmath>
#include <bitset>
using namespace std;
#include "simurgh.h"
using int64 = long long;
int N, M, Q;
vector<vector<int>> eidx;
vector<vector<int>> adj;
vector<int> par;
vector<int> depth;
vector<char> used;
vector<int> status;
vector<int> tree_idx;
vector<int> back_idx;
vector<int> all_idx;
vector<char> added;
int get(int u, int v) {
assert(eidx[u][v] != -1);
return eidx[u][v];
}
void dfs(int n, int p) {
//cerr << n << " " << p << "\n";
used[n] = true;
for (auto v : adj[n]) {
if (v != p) {
int e = get(n, v);
if (!used[v]) {
// Forward edge
par[v] = n;
depth[v] = depth[n] + 1;
tree_idx.push_back(e);
all_idx.push_back(e);
dfs(v, n);
} else if (!added[e]) {
added[e] = true;
back_idx.push_back(e);
all_idx.push_back(e);
}
}
}
}
vector<int> get_cycle(int u, int v) {
vector<int> edges;
auto go_up = [&] (int & el) {
edges.push_back(get(el, par[el]));
el = par[el];
};
while(depth[u] > depth[v]) {
go_up(u);
}
while(depth[u] < depth[v]) {
go_up(v);
}
while(u != v) {
go_up(u);
go_up(v);
}
return edges;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
auto edge_str = [&](int e) {
return to_string(u[e]) + " - " + to_string(v[e]) + " idx: " + to_string(e);
};
N = n;
M = u.size();
adj.resize(N, vector<int>{});
eidx.resize(N, vector<int>(N, -1));
par.resize(N, -1);
used.resize(N, 0);
depth.resize(N, 0);
status.resize(M, -1);
added.resize(M, 0);
for (int i = 0; i < M; i++) {
eidx[ u[i] ][ v[i] ] = eidx[ v[i] ][ u[i] ] = i;
adj[ u[i] ].push_back( v[i] );
adj[ v[i] ].push_back( u[i] );
}
// 1. Find DFS tree
dfs(0, 0);
assert(tree_idx.size() == N - 1);
assert(tree_idx.size() + back_idx.size() == M);
assert(all_idx.size() == M);
// cerr << "tree edges:\n";
for (auto e : tree_idx) {
// cerr << edge_str(e) << "\n";
assert(status[e] == -1);
}
// 50 points
int tree_ans = count_common_roads(tree_idx);
// cerr << "tree_ans: " << tree_ans << "\n";
// 2. Find status of all edges in tree_idx
auto replace = [] (int e, int c, vector<int>& query) {
auto p = find(query.begin(), query.end(), c);
assert(p != query.end());
*p = e;
};
for (auto e : back_idx) {
// get cycle
auto cycle = get_cycle(u[e], v[e]);
int unknown = 0;
for (auto c : cycle)
unknown += (status[c] == -1);
// cerr << "Back edge: " << edge_str(e) << "\n";
// cerr << "cycle\n";
// for (auto c : cycle) {
// cerr << edge_str(c) << "\n";
// }
auto replace_and_query = [&] (int e, int c) {
auto query = tree_idx;
replace(e, c, query);
Q++;
return count_common_roads(query) - tree_ans;
};
if (!unknown) { // all is known
// Just 1 query needed but useless since we want to find out tree_idx
//status[e] = replace_and_query(e, cycle[0]) + status[cycle[0]];
continue;
} else if (unknown < cycle.size()) { // at least one is known
// cerr << "at least one is known\n";
// <= C++14
int cand = -1;
for (auto c : cycle) {
if (status[c] != -1) {
cand = c;
break;
}
}
status[e] = replace_and_query(e, cand) + status[cand];
// use this to find the unknowns
for (auto c : cycle) {
if (status[c] == -1) {
status[c] = -replace_and_query(e, c) + status[e];
}
}
} else { // all is unknown
// cerr << "all is unknown\n";
int neg = 0;
int pos = 0;
for (auto c : cycle) {
status[c] = replace_and_query(e, c);
// cerr << edge_str(c) << " delta: " << status[c] << "\n";
neg += (status[c] < 0);
pos += (status[c] > 0);
}
if (!pos && !neg) {
// cerr << "nothing is different\n";
assert (!pos);
assert (!neg);
for (auto c : cycle) {
status[c] = 0;
}
status[e] = 0;
} else {
assert(!pos || !neg);
if (pos) {
for (auto c : cycle) {
status[c] = 1 - status[c];
}
status[e] = 1;
// cerr << "positive e\n";
} else {
for (auto c : cycle) {
status[c] = -status[c];
}
status[e] = 0;
// cerr << "negative e\n";
}
// cerr << "find out\n";
// for (auto c : cycle) {
// cerr << edge_str(c) << " -> " << status[c] << "\n";
// }
// cerr << "\n";
}
}
}
for (auto e : tree_idx) {
if (status[e] == -1) {
status[e] = 1;
}
}
cerr << "first phase Q: " << Q << "\n";
// 3. Binary search to find remaining edges
vector<int> end_point(M);
for (int n = 0; n < N; n++) {
vector<int> cand_idx;
for (int j = 0; j < N; j++) {
if (eidx[n][j] != -1 && status[get(n, j)] == -1) {
cand_idx.push_back(get(n, j));
end_point[get(n, j)] = j;
}
}
if (!cand_idx.size())
continue;
// auto multi_query = [&](const vector<int> & qset) {
// auto query = tree_idx;
// int delta = 0;
// for (auto e : qset) {
// int re = get(end_point[e], par[end_point[e]]);
// assert(status[re] != -1);
// delta -= status[re];
// replace(e, re, query);
// }
// return count_common_roads(query) - (tree_ans + delta);
// };
auto multi_query = [&](int l, int r) {
auto query = tree_idx;
int delta = 0;
for (int i = l; i <= r; i++) {
auto e = cand_idx[i];
int re = get(end_point[e], par[end_point[e]]);
assert(status[re] != -1);
delta -= status[re];
replace(e, re, query);
}
Q++;
return count_common_roads(query) - (tree_ans + delta);
};
auto full_ans = multi_query(0, cand_idx.size() - 1);
function<void(int, int, int)> Rec = [&] (int l, int r, int tot) {
int m = (l + r) >> 1;
int sz = (r - l + 1);
int left_ans = multi_query(l, m);
int right_ans = tot - left_ans;
auto Continue = [&] (int l1, int r1, int ans) {
int sz = r1 - l1 + 1;
if (!ans) {
for (int i = l1; i <= r1; i++) {
status[cand_idx[i]] = 0;
}
return false;
} else if (ans == sz) {
for (int i = l1; i <= r1; i++) {
status[cand_idx[i]] = 1;
}
return false;
} else {
return true;
}
};
if (Continue(l, m, left_ans)) {
Rec(l, m, left_ans);
}
if (Continue(m + 1, r, right_ans)) {
Rec(m + 1, r, right_ans);
}
};
// REDO
if (!full_ans) {
for (auto e : cand_idx)
status[e] = 0;
} else if (full_ans == cand_idx.size()) {
for (auto e : cand_idx)
status[e] = 1;
} else {
Rec(0, cand_idx.size() - 1, full_ans);
}
}
cerr << "second phase Q: " << Q << "\n";
vector<int> res;
for (auto e : all_idx) {
if (status[e] == 1) {
res.push_back(e);
}
}
assert(res.size() == N - 1);
return res;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from simurgh.cpp:16:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:118:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
118 | assert(tree_idx.size() == N - 1);
| ~~~~~~~~~~~~~~~~^~~~~~~~
simurgh.cpp:119:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
119 | assert(tree_idx.size() + back_idx.size() == M);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
simurgh.cpp:120:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
120 | assert(all_idx.size() == M);
| ~~~~~~~~~~~~~~~^~~~
simurgh.cpp:165:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | } else if (unknown < cycle.size()) { // at least one is known
| ~~~~~~~~^~~~~~~~~~~~~~
simurgh.cpp: In lambda function:
simurgh.cpp:286:17: warning: unused variable 'sz' [-Wunused-variable]
286 | int sz = (r - l + 1);
| ^~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:322:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
322 | } else if (full_ans == cand_idx.size()) {
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from simurgh.cpp:16:
simurgh.cpp:340:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
340 | assert(res.size() == N - 1);
| ~~~~~~~~~~~^~~~~~~~
simurgh.cpp:93:10: warning: variable 'edge_str' set but not used [-Wunused-but-set-variable]
93 | auto edge_str = [&](int e) {
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
correct |
| 2 |
Incorrect |
0 ms |
204 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
