// M
#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
const int N = 505, MXM = N * N / 2;
int n, m, A[MXM], B[MXM], Stat[MXM];
int P[N], PE[N], H[N], F[N], M[N], Back[MXM];
vector < pair < int , int > > Adj[N];
void DFS(int v, int p, int pe)
{
M[v] = 1;
P[v] = p;
PE[v] = pe;
for (auto e : Adj[v])
{
int u = e.first;
int id = e.second;
if (id == pe)
continue;
if (!M[u])
{
H[u] = H[v] + 1;
DFS(u, v, id);
}
else if (M[u] == 1)
{
int nw = v;
while (nw != u)
{
if (Back[PE[nw]] == -1)
Back[PE[nw]] = id;
nw = P[nw];
}
}
}
M[v] = 2;
}
int Find(int v)
{
return (F[v] < 0 ? v : (F[v] = Find(F[v])));
}
inline int Merge(int v, int u)
{
v = Find(v);
u = Find(u);
if (v == u)
return 0;
F[v] = u;
return 1;
}
vector < int > find_roads(int _n, vector < int > _u, vector < int > _v)
{
n = _n;
m = (int)_u.size();
for (int i = 0; i < m; i ++)
A[i] = _u[i], B[i] = _v[i];
for (int i = 0; i < m; i ++)
{
Adj[A[i]].push_back({B[i], i});
Adj[B[i]].push_back({A[i], i});
}
memset(Stat, -1, sizeof(Stat));
memset(Back, -1, sizeof(Back));
DFS(0, -1, -1);
for (int i = 1; i < n; i ++)
if (Stat[PE[i]] == -1)
{
int e = Back[PE[i]];
int v = A[e], u = B[e];
if (H[v] < H[u])
swap(v, u);
int nw = v;
vector < int > V, R;
memset(M, 0, sizeof(M));
while (nw != u)
{
if (Stat[PE[nw]] == -1)
V.push_back(PE[nw]);
else
R.push_back(PE[nw]);
M[nw] = 1;
nw = P[nw];
}
assert((int)V.size());
V.push_back(e);
vector < int > T;
for (int j = 1; j < n; j ++)
if (!M[j])
T.push_back(PE[j]);
if (!R.size())
{
int mn = n, mx = -1;
vector < int > Val(n, 0);
for (int j = 0; j < (int)V.size(); j ++)
{
vector < int > TMp = T;
for (int h = 0; h < (int)V.size(); h ++)
if (j != h)
TMp.push_back(V[h]);
assert((int)TMp.size() == n - 1);
Val[j] = count_common_roads(TMp);
mn = min(mn, Val[j]);
mx = max(mx, Val[j]);
}
if (mn == mx)
for (int j : V)
Stat[j] = 0;
else
{
for (int j = 0; j < (int)V.size(); j ++)
if (Val[j] == mn)
Stat[V[j]] = 1;
else
Stat[V[j]] = 0;
}
}
else
{
vector < int > TMp = T;
for (int j : R)
if (j != R[0])
TMp.push_back(j);
for (int j : V)
TMp.push_back(j);
assert(TMp.size() == n - 1);
int val = count_common_roads(TMp);
for (int j = 0; j < (int)V.size(); j ++)
{
TMp = T;
for (int h = 0; h < (int)V.size(); h ++)
if (j != h)
TMp.push_back(V[h]);
for (int h : R)
TMp.push_back(h);
assert((int)TMp.size() == n - 1);
int cnt = count_common_roads(TMp);
if (cnt < val)
Stat[V[j]] = 1;
else if (cnt > val)
Stat[V[j]] = 0;
else
Stat[V[j]] = Stat[R[0]];
}
}
}
for (int i = 1; i < n; i ++)
assert(Stat[PE[i]] != -1);
for (int i = 1; i <= n; i ++)
{
vector < int > vec;
for (auto u : Adj[i])
if (Stat[u.second] == -1)
vec.push_back(u.second);
auto Ask = [&](int l, int r){
vector < int > TMp;
memset(F, -1, sizeof(F));
for (int j = l; j < r; j ++)
{
TMp.push_back(vec[j]);
Merge(A[vec[j]], B[vec[j]]);
}
int c = 0;
for (int i = 1; i < n; i ++)
if (Merge(i, P[i]))
TMp.push_back(PE[i]), c -= Stat[PE[i]];
c += count_common_roads(TMp);
return c;
};
int d = Ask(0, (int)vec.size());
int le = -1, ri = (int)vec.size(), md;
for (int __ = 0; __ < d; __ ++)
{
le ++;
ri = (int)vec.size();
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (Ask(le, md))
ri = md;
else
le = md;
}
assert(Ask(le, le + 1));
Stat[vec[le]] = 1;
}
for (int id : vec)
if (Stat[id] == -1)
Stat[id] = 0;
}
vector < int > Rs;
for (int i = 0; i < m; i ++)
if (Stat[i])
Rs.push_back(i);
return Rs;
}
Compilation message
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from simurgh.cpp:2:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:129:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
129 | assert(TMp.size() == n - 1);
| ~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1408 KB |
correct |
| 2 |
Correct |
1 ms |
1280 KB |
correct |
| 3 |
Correct |
1 ms |
1280 KB |
correct |
| 4 |
Correct |
1 ms |
1280 KB |
correct |
| 5 |
Correct |
1 ms |
1280 KB |
correct |
| 6 |
Correct |
1 ms |
1280 KB |
correct |
| 7 |
Runtime error |
3 ms |
2560 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1408 KB |
correct |
| 2 |
Correct |
1 ms |
1280 KB |
correct |
| 3 |
Correct |
1 ms |
1280 KB |
correct |
| 4 |
Correct |
1 ms |
1280 KB |
correct |
| 5 |
Correct |
1 ms |
1280 KB |
correct |
| 6 |
Correct |
1 ms |
1280 KB |
correct |
| 7 |
Runtime error |
3 ms |
2560 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1408 KB |
correct |
| 2 |
Correct |
1 ms |
1280 KB |
correct |
| 3 |
Correct |
1 ms |
1280 KB |
correct |
| 4 |
Correct |
1 ms |
1280 KB |
correct |
| 5 |
Correct |
1 ms |
1280 KB |
correct |
| 6 |
Correct |
1 ms |
1280 KB |
correct |
| 7 |
Runtime error |
3 ms |
2560 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
2560 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1408 KB |
correct |
| 2 |
Correct |
1 ms |
1280 KB |
correct |
| 3 |
Correct |
1 ms |
1280 KB |
correct |
| 4 |
Correct |
1 ms |
1280 KB |
correct |
| 5 |
Correct |
1 ms |
1280 KB |
correct |
| 6 |
Correct |
1 ms |
1280 KB |
correct |
| 7 |
Runtime error |
3 ms |
2560 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
