#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 spanning;
const int maxn = 500;
const int maxm = maxn * maxn;
int is_golden[maxm], vis[maxn], parnode[maxn], paredge[maxn];
int depth[maxn], visedge[maxm], maxup[maxn];
vector<p2> up_edges[maxn];
void dfs(int u, vector<vector<p2>>& edges)
{
depth[u] = depth[parnode[u]] + 1;
repe(e, edges[u])
{
if (vis[e.first]) // back edge
{
up_edges[u].push_back(e);
if (visedge[e.second]) continue;
visedge[e.second] = 1;
maxup[u] = min(maxup[u], depth[e.first]);
}
else
{
assert(!visedge[e.second]);
visedge[e.second] = 1;
spanning.push_back(e.second);
vis[e.first] = 1;
parnode[e.first] = u;
paredge[e.first] = e.second;
dfs(e.first, edges);
maxup[u] = min(maxup[u], depth[e.first]);
if (maxup[u]>depth[u]) // bridge
{
is_golden[e.second] = 1;
}
}
}
}
vi a, b;
int n;
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]) == uf.find(b[s])) continue;
uf.merge(a[s], b[s]);
num_good += is_golden[s];
q.push_back(s);
}
assert(sz(q) < n);
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;
rep(i, maxn) maxup[i] = -1;
memset(parnode, -1, sizeof(parnode));
if (n==2)
{
return { 0 };
}
int m = sz(a);
vector<vector<p2>> dedges(n);
rep(i, m)
{
dedges[a[i]].emplace_back(b[i], i);
dedges[b[i]].emplace_back(a[i], i);
}
vis[0] = 1;
parnode[0] = 0;
depth[0] = 0;
dfs(0, dedges);
parnode[0] = -1;
repp(u, 1, n)
{
repe(e, up_edges[u])
{
vi cycle = { e.second };
int v = u;
while (v != -1 && v != e.first)
{
cycle.push_back(paredge[v]);
v = parnode[v];
}
int mx = 0;
vector<p2> res;
rep(i, sz(cycle))
{
UF uf(n);
vi q;
rep(j, sz(cycle))
{
if (i == j) continue;
q.push_back(cycle[j]);
uf.merge(a[cycle[j]], b[cycle[j]]);
}
repe(u, spanning)
{
if (uf.find(a[u]) == uf.find(b[u])) continue;
uf.merge(a[u], b[u]);
q.push_back(u);
}
res.emplace_back(cycle[i], count_common_roads(q));
mx = max(mx, res.back().second);
}
repe(v, res)
{
if (v.second < mx) is_golden[v.first] = 1;
}
}
}
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[j])!=nodes.end()&&nodes.find(b[j])!=nodes.end())
// {
// trongle.push_back(j);
// }
// }
// UF uf(n);
// uf.merge(a[trongle[0]], b[trongle[0]]);
// uf.merge(a[trongle[1]], b[trongle[1]]);
// uf.merge(a[trongle[2]], b[trongle[2]]);
// vi sp;
// rep(e, m)
// {
// if (uf.find(a[e]) == uf.find(b[e])) continue;
// uf.merge(a[e], b[e]);
// sp.push_back(e);
// }
// int m = 0;
// vector<p2> res;
// rep(j, 3)
// {
// vi q;
// rep(k, 3)
// {
// if (j == k) continue;
// q.push_back(trongle[k]);
// }
// repe(s, sp) q.push_back(s);
//
// int r = count_common_roads(q);
// m = max(m, r);
// res.emplace_back(trongle[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, m)
{
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);
}
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;
}
auto start = edges[u].begin();
rep(i, hi) start = next(start);
int e = *start;
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
correct |
| 2 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
