#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 505;
#include "simurgh.h"
map< pair<int,int>, int > id;
int qry(const vector<int> &r) { return count_common_roads(r); }
int pa[MAX_N], dep[MAX_N];
vector<int> edge[MAX_N];
struct dsu {
vector<int> g, sz;
dsu (int n) { g.resize(n+10), sz.resize(n+10, 1), iota(AI(g), 0); }
int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
int S(int i) { return sz[ F(i) ]; }
bool M(int a, int b) {
a = F(a), b = F(b);
if (a == b) return false;
return sz[a] += sz[b], g[b] = a, true;
}
};
void dfs(int x, int lst) {
pa[x] = lst;
for (int u : edge[x]) if (u != lst) {
dep[u] = dep[x] + 1;
dfs(u, x);
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
static int cnt;
assert(++cnt == 1);
int m = u.size();
vector<int> old, on_tree(m);
{
dsu D(n);
for (int i = 0;i < m;++i) {
id[ {u[i], v[i]} ] = i;
id[ {v[i], u[i]} ] = i;
if (D.M(v[i], u[i])) {
edge[ u[i] ].pb( v[i] );
edge[ v[i] ].pb( u[i] );
old.pb(i);
on_tree[i] = true;
}
}
}
dfs(0, 0);
int old_val = qry(old);
dsu D(m + 2);
int Z = m, O = m+1;
auto sure = [&](int a) {
return D.F(a) == D.F(Z) || D.F(a) == D.F(O);
};
for (int i = 0;i < m;++i) {
if (on_tree[i]) continue;
int a = u[i], b = v[i];
vector<int> all;
while (a != b) {
if (dep[a] < dep[b]) swap(a, b);
all.pb( id[ {a, pa[a]} ] );
a = pa[a];
}
for (int j : all) {
if (sure(i) && sure(j)) continue;
if (D.F(i) == D.F(j)) continue;
vector<int> now = old;
now.erase(find(AI(now), j));
now.pb(i);
int nv = qry(now);
if (nv == old_val) D.M(i, j);
if (nv > old_val) D.M(i, O), D.M(j, Z);
if (nv < old_val) D.M(i, Z), D.M(j, O);
}
if (D.S(O) == n) break;
}
for (int i = 0;i < m;++i) if (D.S(i) == 1)
D.M(i, O);
vector<int> res;
for (int i = 0;i < m;++i) {
if (D.F(i) == D.F(O))
res.pb(i);
}
assert(res.size() == n-1);
return res;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from simurgh.cpp:1:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:120:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
120 | assert(res.size() == n-1);
| ~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
correct |
| 2 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
