#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll linf = ll(1e18);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif
struct UF
{
vi par;
UF(int n) : par(n)
{
rep(i, n)par[i] = i;
}
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
void merge(int a, int b)
{
a = find(a); b = find(b);
if (a == b) return;
par[b] = a;
}
};
vi a, b;
int n;
vector<p2> spanning;
int forest_query(vi edges)
{
vi q;
UF uf(n);
repe(u, edges)
{
q.emplace_back(u);
if (uf.find(a[u]) == uf.find(b[u])) assert(0);
uf.merge(a[u], b[u]);
}
int num_good = 0;
repe(s, spanning)
{
if (uf.find(a[s.first]) == uf.find(b[s.first])) continue;
num_good += s.second;
q.push_back(s.first);
}
return count_common_roads(q) - num_good;
}
std::vector<int> find_roads(int N, std::vector<int> A, std::vector<int> B) {
a = A;
b = B;
n = N;
if (n==2)
{
return { 0 };
}
int m = sz(a);
UF uf(n);
vvi adj(n);
rep(i, m)
{
if (uf.find(a[i]) != uf.find(b[i]))
{
uf.merge(a[i], b[i]);
spanning.emplace_back(i, -1);
adj[a[i]].push_back(i);
adj[b[i]].push_back(i);
}
}
assert(sz(spanning) == n - 1);
vi q(n - 1);
rep(i, n-1)
{
int eind = spanning[i].first;
vi trongle;
int u = a[eind];
int v = b[eind];
trongle.push_back(eind);
repe(e, adj[u])
{
if (e != eind)
{
trongle.push_back(e);
break;
}
}
if (sz(trongle)==1)
{
repe(e, adj[v])
{
if (e != eind)
{
trongle.push_back(e);
break;
}
}
}
set<int> nodes;
nodes.insert(a[trongle[0]]);
nodes.insert(b[trongle[0]]);
nodes.insert(a[trongle[1]]);
nodes.insert(b[trongle[1]]);
trongle = vi();
rep(j, m)
{
if (nodes.find(a[i])!=nodes.end()&&nodes.find(b[i])!=nodes.end())
{
trongle.push_back(j);
}
}
int m = 0;
vector<p2> res;
rep(j, 3)
{
vi q;
rep(k, n - 1)
{
if (find(all(trongle), spanning[k].first) != trongle.end()) continue;
q.push_back(spanning[k].first);
}
rep(k, 3)
{
if (j == k) continue;
q.push_back(trongle[k]);
}
int r = count_common_roads(q);
m = max(m, r);
res.emplace_back(j, r);
}
rep(j, 3)
{
if (res[j].first == eind)
{
spanning[i].second = res[j].second < m;
break;
}
}
}
vector<set<int>> edges(n);
rep(i, n)
{
edges[a[i]].insert(i);
edges[b[i]].insert(i);
}
queue<int> leaf;
vi deg(n);
rep(i, n)
{
deg[i] = forest_query(vi(all(edges[i])));
if (deg[i] == 1) leaf.push(i);
}
int baseline = forest_query(vi());
vi par(n, -1);
while (sz(leaf))
{
int u = leaf.front();
leaf.pop();
if (deg[u] == 0) break;
assert(deg[u] == 1);
int lo = -1;
int hi = sz(edges[u]);
while (lo+1<hi)
{
int mid = (lo + hi) / 2;
vi q;
auto start = edges[u].begin();
rep(i, mid + 1)
{
q.push_back(*start);
start++;
}
if (forest_query(q))
{
hi = mid;
}
else lo = mid;
}
int e = *next(edges[u].begin(),hi);
int v = a[e] == u ? b[e] : a[e];
edges[v].erase(e);
deg[v]--;
if (deg[v]==1)
{
leaf.push(v);
}
par[u] = e;
}
vi r;
rep(i, n) if (par[i] != -1)r.push_back(par[i]);
int common = count_common_roads(r);
assert(common == n - 1);
return r;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:175:6: warning: unused variable 'baseline' [-Wunused-variable]
175 | int baseline = forest_query(vi());
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
correct |
| 2 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
