#include <bits/stdc++.h>
#include "simurgh.h"
//#include "Lgrader.cpp"
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 9);
const int MAXM = (1 << 18);
struct dsu
{
int par[MAXN], sz[MAXN];
void init(int n)
{
for(int i = 0; i <= n; i++)
par[i] = i, sz[i] = 1;
}
int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); }
bool connected(int x, int y) { return root(x) == root(y); }
void unite(int u, int v)
{
u = root(u);
v = root(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
}
} d;
int m, n;
pair<int, int> ed[MAXM];
vector<pair<int, int> > adj[MAXN];
int dfs_time, low[MAXN], disc[MAXN];
int low_edge[MAXN], ver[MAXN];
int E[MAXN];
int par[MAXN], pe[MAXN];
vector<int> li[MAXM];
vector<int> le, Tr;
bool cmp(int i, int j) { return min(low[ed[i].first], low[ed[i].second]) < min(low[ed[j].first], low[ed[j].second]); }
void tarjan(int u, int pr)
{
low[u] = disc[u] = ++dfs_time;
ver[dfs_time] = u;
low_edge[u] = -1;
for(auto e: adj[u])
if(e.first != pr)
{
int v = e.first;
if(!disc[v])
{
par[v] = u;
pe[v] = e.second;
tarjan(v, u);
if(chkmin(low[u], low[v]))
low_edge[u] = low_edge[v];
if(disc[u] < low[v])
E[e.second] = 1;
}
else if(chkmin(low[u], disc[v]))
low_edge[u] = e.second;
}
if(low_edge[u] != -1)
le.push_back(low_edge[u]);
if(u != pr) Tr.push_back(pe[u]);
}
int R[MAXM];
int initial;
int diff(int rem, int add)
{
vector<int> tmp;
for(int e: Tr)
if(e == rem) tmp.push_back(add);
else tmp.push_back(e);
return count_common_roads(tmp) - initial;
}
int cnt_good(vector<int> L)
{
d.init(::n);
vector<int> tmp = L;
for(int i: L)
d.unite(ed[i].first, ed[i].second);
int to_rem = 0;
for(int i: Tr)
if(!d.connected(ed[i].first, ed[i].second))
to_rem += E[i], d.unite(ed[i].first, ed[i].second), tmp.push_back(i);
return count_common_roads(tmp) - to_rem;
}
void rec(vector<int> &l, int sum)
{
if(sum == 0)
return;
if(l.size() == 1)
{
E[l.back()] = 1;
return;
}
vector<int> m1, m2;
for(int i = 0; i < (int)l.size() / 2; i++) m1.push_back(l[i]);
for(int i = l.size() / 2; i < (int)l.size(); i++) m2.push_back(l[i]);
int c1 = cnt_good(m1), c2 = sum - c1;
rec(m1, c1);
rec(m2, c2);
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
::n = n;
::m = u.size();
for(int i = 0; i < ::m; i++)
{
ed[i] = {u[i], v[i]};
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
E[i] = -1;
}
tarjan(0, 0);
sort(le.begin(), le.end());
le.erase(unique(le.begin(), le.end()), le.end());
sort(le.begin(), le.end(), cmp);
initial = count_common_roads(Tr);
for(int i: le)
{
int from = ed[i].first, to = ed[i].second;
if(disc[from] > disc[to]) swap(from, to);
while(to != from)
{
li[i].push_back(pe[to]);
to = par[to];
}
int has = -1;
for(int e: li[i])
if(E[e] != -1)
has = e;
if(has != -1)
{
int df = diff(has, i);
if(df == 0) E[i] = E[has];
else E[i] = E[has] ^ 1;
for(int e: li[i])
if(E[e] == -1)
{
int df = diff(e, i);
if(df == 0) E[e] = E[i];
else E[e] = E[i] ^ 1;
}
}
else
{
bool fl = 0;
for(int e: li[i])
{
R[e] = diff(e, i);
if(R[e]) fl = 1;
}
if(!fl)
{
E[i] = 0;
for(int e: li[i])
E[e] = 0;
}
else
{
for(int e: li[i])
if(R[e])
{
if(R[e] == 1) E[i] = 1;
else E[i] = 0;
break;
}
for(int e: li[i])
if(E[e] == -1)
{
int df = R[e];
if(df == 0) E[e] = E[i];
else E[e] = E[i] ^ 1;
}
}
}
}
return vector<int>();
for(int i = 0; i < n; i++)
{
int cnt = 0;
vector<int> candidates;
for(auto e: adj[i])
if(E[e.second] == -1)
candidates.push_back(e.second);
cnt = cnt_good(candidates);
rec(candidates, cnt);
}
vector<int> result;
for(int i = 0; i < ::m; i++)
if(E[i] == 1)
result.push_back(i);
return result;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6520 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6520 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6520 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
6520 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6520 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
