#include "simurgh.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
typedef long long llong;
const int MAXN = 500 + 12;
namespace
{
int n;
int dep[MAXN];
int par[MAXN];
bool vis[MAXN];
int idx[MAXN][MAXN];
int covering[MAXN][MAXN];
bool queried[MAXN][MAXN];
bool isIn[MAXN][MAXN];
bool isInTree[MAXN][MAXN];
std::vector <int> g[MAXN];
std::vector <int> t[MAXN];
std::vector <std::pair <int,int>> byCovering[MAXN * MAXN];
std::vector <std::pair <int,int>> inTreeEdges;
std::vector <int> inTree;
}
struct DSU
{
int par[MAXN];
int dep[MAXN];
void reset()
{
std::iota(par, par + n, 0);
std::fill(dep, dep + n, 1);
}
int find(int node)
{
if (par[node] == node) return node;
return par[node] = find(par[node]);
}
void connect(int u, int v)
{
u = find(u);
v = find(v);
assert(u != v);
if (u == v)
{
return;
}
if (dep[u] > dep[v])
{
std::swap(u, v);
}
if (dep[u] == dep[v])
{
dep[v]++;
}
par[u] = v;
}
bool areConnected(int u, int v)
{
return find(u) == find(v);
}
};
DSU dsu;
void depthDFS(int node, int p)
{
par[node] = p;
vis[node] = true;
for (const int &u : g[node])
{
if (u == p || vis[u])
{
continue;
}
dep[u] = dep[node] + 1;
t[node].push_back(u);
isInTree[node][u] = true;
isInTree[u][node] = true;
inTree.push_back(idx[u][node]);
inTreeEdges.push_back({u, node});
depthDFS(u, node);
}
}
void apply(int u, int v, int idx)
{
if (u == v)
{
return;
}
byCovering[idx].push_back({u, par[u]});
covering[u][par[u]] = idx;
apply(par[u], v, idx);
}
void dfsCovering(int node)
{
if (node != 0)
{
if (covering[node][par[node]] == -1)
{
isIn[node][par[node]] = true;
isIn[par[node]][node] = true;
}
}
for (const int &u : t[node])
{
dfsCovering(u);
}
}
int treeIncluding(std::vector <std::pair <int,int>> &edges)
{
dsu.reset();
std::vector <int> indices;
// std::cout << "tree including:\n";
// for (const auto &[u, v] : edges)
// {
// std::cout << u << ' ' << v << '\n';
// }
// std::cout << std::flush;
for (const auto &[u, v] : edges)
{
assert(!dsu.areConnected(u, v));
dsu.connect(u, v);
indices.push_back(idx[u][v]);
}
int sub = 0;
for (const auto &[u, v] : inTreeEdges)
{
if (dsu.areConnected(u, v))
{
continue;
}
sub += isIn[u][v];
indices.push_back(idx[u][v]);
dsu.connect(u, v);
}
return count_common_roads(indices) - sub;
}
std::vector <int> find_roads(int n, std::vector <int> u, std::vector <int> v)
{
::n = n;
memset(idx, -1, sizeof(idx));
memset(covering, -1, sizeof(idx));
for (int i = 0 ; i < u.size() ; ++i)
{
idx[u[i]][v[i]] = i;
idx[v[i]][u[i]] = i;
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
depthDFS(0, -1);
// std::cout << "in tree\n";
// for (const auto &[u, v] : inTreeEdges)
// {
// std::cout << u << ' ' << v << '\n';
// }
for (int i = 0 ; i < u.size() ; ++i)
{
if (isInTree[u[i]][v[i]])
{
continue;
}
if (dep[u[i]] > dep[v[i]]) apply(u[i], v[i], i);
else apply(v[i], u[i], i);
}
dfsCovering(0);
int globalTreeCount = count_common_roads(inTree);
if (globalTreeCount == n - 1)
{
return inTree;
}
for (int coverIdx = 0 ; coverIdx < u.size() ; ++coverIdx)
{
if (byCovering[coverIdx].empty())
{
continue;
}
int res = globalTreeCount;
std::vector <int> sols;
bool foundMAX = false;
for (int i = 0 ; i < byCovering[coverIdx].size() ; ++i)
{
if (queried[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second] && (foundMAX || !isIn[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second]))
{
sols[i] = MAXN;
continue;
}
std::vector <int> curr = inTree;
for (int &j : curr)
{
if (j == idx[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second])
{
std::swap(j, curr.back());
curr.pop_back();
break;
}
}
curr.push_back(coverIdx);
sols.push_back(count_common_roads(curr));
res = std::max(res, sols.back());
if (queried[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second])
{
foundMAX = true;
}
queried[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second] = true;
}
// std::cout << "here: " << coverIdx << ' ' << byCovering[coverIdx].size() << '\n';
for (int i = 0 ; i < byCovering[coverIdx].size() ; ++i)
{
// std::cout <<
if (sols[i] < res)
{
// std::cout << "in golden set: " << byCovering[coverIdx][i].first << ' ' << byCovering[coverIdx][i].second << '\n';
isIn[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second] = true;
isIn[byCovering[coverIdx][i].second][byCovering[coverIdx][i].first] = true;
}
}
}
for (int u = 0 ; u < n ; ++u)
{
std::vector <std::pair <int,int>> allEdges;
for (const int &v : g[u])
{
if (isInTree[u][v] || v < u)
{
continue;
}
allEdges.push_back({u, v});
}
int lastPos = -1;
int countFound = 0;
int cnt = treeIncluding(allEdges);
// std::cout << "cnt for: " << u << " = " << cnt << '\n';
while (cnt--)
{
int l = lastPos, r = allEdges.size(), mid;
while (l < r - 1)
{
mid = l + r >> 1;
std::vector <std::pair <int,int>> curr;
for (int i = 0 ; i <= mid ; ++i)
{
curr.push_back(allEdges[i]);
}
if (treeIncluding(curr) <= countFound) l = mid;
else r = mid;
}
assert(r < allEdges.size());
isIn[u][allEdges[r].second] = true;
isIn[allEdges[r].second][u] = true;
countFound++;
lastPos = r;
}
}
std::vector <int> sol;
for (int i = 0 ; i < n ; ++i)
{
for (int j = i + 1 ; j < n ; ++j)
{
if (isIn[i][j])
{
sol.push_back(idx[i][j]);
}
}
}
return sol;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:167:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for (int i = 0 ; i < u.size() ; ++i)
| ~~^~~~~~~~~~
simurgh.cpp:182:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
182 | for (int i = 0 ; i < u.size() ; ++i)
| ~~^~~~~~~~~~
simurgh.cpp:200:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
200 | for (int coverIdx = 0 ; coverIdx < u.size() ; ++coverIdx)
| ~~~~~~~~~^~~~~~~~~~
simurgh.cpp:210:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
210 | for (int i = 0 ; i < byCovering[coverIdx].size() ; ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:242:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
242 | for (int i = 0 ; i < byCovering[coverIdx].size() ; ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:276:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
276 | mid = l + r >> 1;
| ~~^~~
In file included from /usr/include/c++/10/cassert:44,
from simurgh.cpp:5:
simurgh.cpp:287:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
287 | assert(r < allEdges.size());
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
18776 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
18776 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
18776 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9308 KB |
correct |
| 2 |
Runtime error |
11 ms |
18588 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
18776 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
