#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, u[124750], v[124750];
vector<pair<int, int>> graph[500];
int tin[500], low[500], timer = 0, deg[500], cmp[500];
bool visited[500], known[124750], is_golden[124750];
pair<int, int> back_edge[500], par[500];
vector<int> dfs_tree;
void dfs(int node = 0, int parent = -1) {
visited[node] = true;
tin[node] = low[node] = timer++;
for (pair<int, int> i : graph[node]) if (i.first != parent) {
if (visited[i.first]) {
low[node] = min(low[node], tin[i.first]);
if (tin[node] > tin[i.first]) back_edge[node] = i;
} else {
dfs(i.first, node);
low[node] = min(low[node], low[i.first]);
if (low[i.first] > tin[node])
known[i.second] = is_golden[i.second] = true;
dfs_tree.push_back(i.second);
par[i.first] = {node, i.second};
}
}
}
int find(int A) { return cmp[A] = (A == cmp[A] ? A : find(cmp[A])); }
void onion(int A, int B) { cmp[find(A)] = find(B); }
int query_forest(vector<int> forest) {
iota(cmp, cmp + n, 0);
for (int i : forest) onion(u[i], v[i]);
int delta = 0;
for (int i : dfs_tree) if (find(u[i]) != find(v[i])) {
delta -= is_golden[i];
forest.push_back(i);
onion(u[i], v[i]);
}
return count_common_roads(forest) + delta;
}
vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) {
n = _n, m = _u.size();
for (int i = 0; i < m; i++) {
u[i] = _u[i], v[i] = _v[i];
graph[u[i]].push_back({v[i], i});
graph[v[i]].push_back({u[i], i});
}
// First, we find the status of all edges in the DFS tree
fill_n(back_edge, n, make_pair(-1, -1));
dfs();
int dfs_tree_common = count_common_roads(dfs_tree);
for (int i = 0; i < n; i++) if (~back_edge[i].first) {
int curr = i;
bool single_known = false;
vector<int> unknown;
while (curr != back_edge[i].first) {
if (!known[par[curr].second])
unknown.push_back(par[curr].second);
else if (!single_known) {
single_known = true;
unknown.push_back(par[curr].second);
}
curr = par[curr].first;
}
vector<int> query_res;
for (int j : unknown) {
vector<int> to_query = {back_edge[i].second};
for (int k : dfs_tree) if (k != j) to_query.push_back(k);
query_res.push_back(count_common_roads(to_query));
}
int mx = max(dfs_tree_common, *max_element(query_res.begin(), query_res.end()));
for (int i = 0; i < unknown.size(); i++) {
known[unknown[i]] = true;
is_golden[unknown[i]] = (query_res[i] != mx);
}
}
// Next, we get the "degree" of each node in the golden tree
queue<int> q;
for (int i = 0; i < n; i++) {
vector<int> to_query;
for (pair<int, int> j : graph[i]) to_query.push_back(j.second);
deg[i] = query_forest(to_query);
if (deg[i] == 1) q.push(i);
}
// Finally, binary search for the "parent" of each node
while (q.size()) {
int curr = q.front();
q.pop();
if (deg[curr] != 1) continue;
int l = 0, r = graph[curr].size() - 1;
while (l != r) {
int mid = (l + r) / 2;
vector<int> to_query;
for (int i = l; i <= mid; i++) to_query.push_back(graph[curr][i].second);
if (query_forest(to_query)) r = mid;
else l = mid + 1;
}
int nxt, id;
tie(nxt, id) = graph[curr][l];
is_golden[id] = true;
deg[nxt]--;
if (deg[nxt] == 1) q.push(nxt);
vector<pair<int, int>> tmp;
for (pair<int, int> i : graph[nxt]) if (i.second != id) tmp.push_back(i);
graph[nxt] = tmp;
}
// Return the answer
vector<int> ans;
for (int i = 0; i < m; i++) if (is_golden[i]) ans.push_back(i);
return ans;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0; i < unknown.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
320 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
137 ms |
4676 KB |
correct |
| 4 |
Correct |
208 ms |
6576 KB |
correct |
| 5 |
Correct |
211 ms |
6660 KB |
correct |
| 6 |
Incorrect |
208 ms |
6716 KB |
WA in grader: NO |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
