#include "simurgh.h"
#include <cassert>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = 240 + 2;
int n;
int eid[N][N];
bool royal[N][N];
struct TEdge { int u, v, id; };
vector<TEdge> el;
vector<TEdge*> SpanningTree(const vector<TEdge*> &elist)
{
vector<int> cpn(n);
for (int i = 0; i < n; ++i) cpn[i] = i;
vector<TEdge*> ret;
for (auto e: elist)
if (cpn[e->u] != cpn[e->v])
{
int old_cpn = cpn[e->v];
for (int i = 0; i < n; ++i)
if (cpn[i] == old_cpn) cpn[i] = cpn[e->u];
ret.push_back(e);
}
return ret;
}
int col[N];
vector<int> g[N];
void Dfs(int u)
{
for (int v: g[u])
if (col[v] == -1)
{
col[v] = col[u];
Dfs(v);
}
}
vector<int> find_roads(int n_, vector<int> roadsU, vector<int> roadsV)
{
n = n_;
int m = roadsU.size();
for (int i = 0; i < n; ++i)
fill(eid[i], eid[i] + n, -1);
for (int i = 0; i < m; ++i)
{
int u = roadsU[i], v = roadsV[i];
el.push_back({u, v, i});
eid[u][v] = eid[v][u] = i;
}
for (int i = 0; i < n; ++i)
{
vector<TEdge*> span;
for (auto &e: el)
if (e.u != i && e.v != i) span.push_back(&e);
for (auto &e: el)
if (e.u == i || e.v == i) span.push_back(&e);
vector<TEdge*> base = SpanningTree(span);
assert(base.size() == n - 1);
/* if (i == -1) cout << base[0]; */
for (int j = 0; j < n; ++j) g[j].clear(), col[j] = -1;
set<int> ids;
for (auto e: base)
{
g[e->u].push_back(e->v);
g[e->v].push_back(e->u);
ids.insert(e->id);
}
col[i] = i;
for (int v: g[i]) if (col[v] == -1) col[v] = v, Dfs(v);
int baseCnt = count_common_roads(vector<int>(ids.begin(), ids.end()));
for (int u: g[i])
{
int posiCnt = -1;
if (u < i) posiCnt = baseCnt + !royal[i][u];
for (int v = 0; posiCnt == -1 && v < i; ++v)
if (col[v] == u && eid[i][v] != -1)
{
ids.erase(eid[i][u]);
ids.insert(eid[i][v]);
posiCnt = count_common_roads(vector<int>(ids.begin(), ids.end()));
ids.erase(eid[i][v]);
ids.insert(eid[i][u]);
}
vector<int> adj;
if (posiCnt == -1)
{
int mx = baseCnt;
adj.push_back(u);
for (int v = i + 1; v < n; ++v)
if (col[v] == u && eid[i][v] != -1)
{
ids.erase(eid[i][u]);
ids.insert(eid[i][v]);
int inq = count_common_roads(vector<int>(ids.begin(), ids.end()));
if (inq > mx) adj.clear(), mx = inq;
if (inq == mx) adj.push_back(v);
ids.erase(eid[i][v]);
ids.insert(eid[i][u]);
}
}
else
for (int v = i + 1; v < n; ++v)
if (col[v] == u && eid[i][v] != -1)
{
ids.erase(eid[i][u]);
ids.insert(eid[i][v]);
if (count_common_roads(vector<int>(ids.begin(), ids.end())) == posiCnt) adj.push_back(v);
ids.erase(eid[i][v]);
ids.insert(eid[i][u]);
}
for (int v: adj)
royal[i][v] = royal[v][i] = true;
}
}
vector<int> res;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (royal[i][j]) res.push_back(eid[i][j]);
return res;
}
Compilation message
In file included from /usr/include/c++/7/cassert:44:0,
from simurgh.cpp:3:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:68:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(base.size() == n - 1);
~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
correct |
| 2 |
Incorrect |
2 ms |
356 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
correct |
| 2 |
Incorrect |
2 ms |
356 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
correct |
| 2 |
Incorrect |
2 ms |
356 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
436 KB |
correct |
| 2 |
Incorrect |
3 ms |
472 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
correct |
| 2 |
Incorrect |
2 ms |
356 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
