#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
struct disjoint_set_union
{
int par[maxn];
disjoint_set_union() {};
disjoint_set_union(int n)
{
for (int i = 0; i < n; i ++)
par[i] = i;
}
int find_leader(int v)
{
if (v == par[v])
return v;
return (par[v] = find_leader(par[v]));
}
bool is_connected(int v, int u)
{
return find_leader(v) == find_leader(u);
}
void unite(int v, int u)
{
v = find_leader(v);
u = find_leader(u);
if (v == u)
return;
par[v] = u;
}
};
int is_bridge[maxn * maxn];
int direction[maxn * maxn];
vector < pair < int, int > > adj[maxn];
int par[maxn], par_idx[maxn], used[maxn];
int depth[maxn];
void dfs(int v)
{
used[v] = 1;
for (pair < int, int > nb : adj[v])
{
if (nb.first == par[v])
continue;
if (!used[nb.first])
{
par_idx[nb.first] = nb.second;
par[nb.first] = v;
direction[nb.second] = 1;
depth[nb.first] = depth[v] + 1;
dfs(nb.first);
}
else
{
direction[nb.second] = -1;
}
}
}
vector < vector < int > > cycles;
vector < int > gold;
int visit[maxn * maxn], is_gold[maxn * maxn];
vector < int > span;
vector < int > tree;
void trav(int v)
{
for (pair < int, int > nb : adj[v])
{
if (used[nb.first] == 0)
{
used[nb.first] = 1;
tree.push_back(nb.second);
trav(nb.first);
}
}
}
int N, M;
pair < int, int > ed[maxn * maxn];
vector < int > out[maxn];
int delta_gold(vector < int > edges)
{
vector < int > res;
res = edges;
disjoint_set_union dsu(N);
for (int i = 0; i < edges.size(); i ++)
dsu.unite(ed[edges[i]].first, ed[edges[i]].second);
int new_gold = 0;
for (int i = 0; i < edges.size(); i ++)
if (is_gold[edges[i]] == 1)
new_gold --;
for (int i = 0; i < span.size(); i ++)
{
int idx = span[i];
int v = ed[idx].first, u = ed[idx].second;
if (!dsu.is_connected(v, u))
{
dsu.unite(v, u);
if (is_gold[idx] == 1)
{
///cout << "--- " << v << " " << u << endl;
new_gold --;
}
res.push_back(idx);
}
}
///cout << "delta" << endl;
for (int i = 0; i < res.size(); i ++)
{
int idx = res[i];
///cout << ed[idx].first << " -- " << ed[idx].second << endl;
}
///cout << new_gold << endl;
new_gold = new_gold + count_common_roads(res);
return new_gold;
}
int deg[maxn];
vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
int m = u.size();
N = n;
M = m;
for (int i = 0; i < m; i ++)
{
ed[i] = {u[i], v[i]};
}
for (int i = 0; i < m; i ++)
{
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
par[0] = -1;
par_idx[0] = -1;
dfs(0);
for (int i = 0; i < m; i ++)
{
int V = u[i], U = v[i];
if (direction[i] == -1)
{
if (depth[V] < depth[U])
swap(V, U);
vector < int > cycle;
int cur = V;
while(cur != U)
{
visit[par_idx[cur]] = 1;
cycle.push_back(par_idx[cur]);
cur = par[cur];
}
visit[i] = 1;
cycle.push_back(i);
cycles.push_back(cycle);
}
}
/**cout << "--------------" << endl;
for (int i = 0; i < m; i ++)
{
if (direction[i] == 1)
cout << u[i] << " : " << v[i] << endl;
}
cout << "-------------" << endl;*/
for (int i = 0; i < m; i ++)
{
if (!visit[i])
{
gold.push_back(i);
span.push_back(i);
is_gold[i] = 1;
}
else
{
if (direction[i] == 1)
span.push_back(i);
}
}
for (vector < int > cycle : cycles)
{
for (int i = 0; i < n; i ++)
used[i] = 0;
bool need = false;
int mx = -1;
for (int i = 0; i < cycle.size() - 1; i ++)
{
int edge = cycle[i];
if (is_gold[edge] == 0)
need = true;
else
mx = edge;
used[v[edge]] = used[u[edge]] = 2;
}
if (!need)
continue;
tree.clear();
for (int i = 0; i < n; i ++)
{
if (used[i] == 2)
trav(i);
}
if (mx == -1)
{
vector < int > values;
int max_val = -1, min_val = 1e9;
for (int i = 0; i < cycle.size(); i ++)
{
vector < int > res = tree;
for (int j = 0; j < cycle.size(); j ++)
{
if (i != j)
res.push_back(cycle[j]);
}
values.push_back(count_common_roads(res));
max_val = max(max_val, values.back());
min_val = min(min_val, values.back());
}
if (max_val == min_val)
{
for (int idx : cycle)
is_gold[idx] = -1;
}
else
{
for (int i = 0; i < cycle.size(); i ++)
{
if (values[i] == min_val)
is_gold[cycle[i]] = 1;
else
is_gold[cycle[i]] = -1;
}
}
}
else
{
/** cout << "base" << endl;
for (int i = 0; i < cycle.size(); i ++)
{
int idx = cycle[i];
cout << u[idx] << " " << v[idx] << endl;
}*/
int max_val = 0, min_val = 1e9;
vector < int > res = tree;
for (int i = 0; i < cycle.size(); i ++)
if (i != mx)
res.push_back(cycle[i]);
int val = count_common_roads(res);
if (is_gold[cycle[mx]] == 1)
{
min_val = val;
max_val = val + 1;
}
else
{
min_val = val - 1;
max_val = val;
}
for (int i = 0; i < cycle.size() - 1; i ++)
{
if (is_gold[cycle[i]] == 0)
{
res = tree;
for (int j = 0; j < cycle.size(); j ++)
if (j != i)
res.push_back(cycle[j]);
val = count_common_roads(res);
if (val == max_val)
is_gold[cycle[i]] = -1;
else
is_gold[cycle[i]] = 1;
}
}
}
}
queue < int > q;
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < m; j ++)
{
if (v[j] == i || u[j] == i)
out[i].push_back(j);
}
deg[i] = delta_gold(out[i]);
if (deg[i] == 1)
q.push(i);
}
/**cout << "Span" << endl;
for (int i = 0; i < span.size(); i ++)
{
int idx = span[i];
cout << u[idx] << " : " << v[idx] << " " << is_gold[idx] << endl;
}*/
//cout << delta_gold(out[1]) << endl;
//exit(0);
while(!q.empty())
{
int cur = q.front();
q.pop();
if (deg[cur] == 0)
continue;
int l = 0, r = out[cur].size() - 1;
while(l <= r)
{
int m = (l + r) / 2;
vector < int > st;
for (int i = 0; i <= m; i ++)
st.push_back(out[cur][i]);
if (delta_gold(st) > 0)
r = m - 1;
else
l = m + 1;
}
is_gold[out[cur][l]] = 1;
int oth = u[out[cur][l]];
if (oth == cur)
oth = v[out[cur][l]];
deg[oth] --;
deg[cur] --;
if (deg[oth] == 1)
q.push(oth);
}
vector < int > ans;
for (int i = 0; i < m; i ++)
if (is_gold[i] == 1)
ans.push_back(i);
return ans;
}
Compilation message
simurgh.cpp: In function 'int delta_gold(std::vector<int>)':
simurgh.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int i = 0; i < edges.size(); i ++)
| ~~^~~~~~~~~~~~~~
simurgh.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int i = 0; i < edges.size(); i ++)
| ~~^~~~~~~~~~~~~~
simurgh.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i = 0; i < span.size(); i ++)
| ~~^~~~~~~~~~~~~
simurgh.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int i = 0; i < res.size(); i ++)
| ~~^~~~~~~~~~~~
simurgh.cpp:121:13: warning: unused variable 'idx' [-Wunused-variable]
121 | int idx = res[i];
| ^~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:199:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for (int i = 0; i < cycle.size() - 1; i ++)
| ~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:225:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
225 | for (int i = 0; i < cycle.size(); i ++)
| ~~^~~~~~~~~~~~~~
simurgh.cpp:228:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
228 | for (int j = 0; j < cycle.size(); j ++)
| ~~^~~~~~~~~~~~~~
simurgh.cpp:245:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
245 | for (int i = 0; i < cycle.size(); i ++)
| ~~^~~~~~~~~~~~~~
simurgh.cpp:265:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
265 | for (int i = 0; i < cycle.size(); i ++)
| ~~^~~~~~~~~~~~~~
simurgh.cpp:281:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
281 | for (int i = 0; i < cycle.size() - 1; i ++)
| ~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:286:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
286 | for (int j = 0; j < cycle.size(); j ++)
| ~~^~~~~~~~~~~~~~
simurgh.cpp:263:30: warning: variable 'min_val' set but not used [-Wunused-but-set-variable]
263 | int max_val = 0, min_val = 1e9;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
correct |
| 2 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
correct |
| 2 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
correct |
| 2 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Incorrect |
0 ms |
340 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
correct |
| 2 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
