#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
#define F first
#define S second
const int N = 506, M = N * N;
set <int> st;
vector <pii> g[N];
bool vis[N];
int h[N], par[N];
int a[M], b[M];
int w[M];
vector <int> tree;
int p[N], sz[N];
int d[N];
int nn;
bool ff[M];
int get_par (int v) {
if (p[v] == v)
return v;
return p[v] = get_par (p[v]);
}
bool merge(int u, int v) {
u = get_par (u);
v = get_par (v);
if (u == v)
return false;
if (sz[u] > sz[v])
swap (u, v);
p[u] = v;
return true;
}
void clear() {
for (int i = 0; i < N; i++) {
p[i] = i;
sz[i] = 1;
}
}
int cc = 0;
int askt () {
cc++;
if (cc >= 8000)
assert (false);
vector <int> wef;
for (int x : st)
wef.push_back(x);
return count_common_roads(wef);
}
void dfs (int v) {
vis[v] = true;
for (pii p : g[v]) {
int u = p.F;
if (!vis[u]) {
h[u] = h[v] + 1;
par[u] = p.S;
dfs (u);
tree.push_back (p.S);
st.insert (p.S);
}
}
}
int askj (vector <int> wef) {
clear();
for (int i : wef) {
assert (merge (a[i], b[i]));
}
int k = 0;
for (int i : tree) {
if (merge (a[i], b[i])) {
wef.push_back (i);
k += w[i];
}
}
assert (wef.size() == nn - 1);
int wefwef = count_common_roads (wef) - k;
return wefwef;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
nn = n;
int m = (int)u.size();
for (int i = 0; i < m; i++) {
w[i] = -1;
a[i] = u[i];
b[i] = v[i];
g[a[i]].push_back(make_pair (b[i], i));
g[b[i]].push_back(make_pair (a[i], i));
}
dfs (0);
int k = askt();
for (int i = 0; i < m; i++) {
if (abs (h[a[i]] - h[b[i]]) >= 2) {
if (h[a[i]] < h[b[i]])
swap (a[i], b[i]);
vector <int> alo;
int vv = a[i];
bool f = false;
int h = -1;
while (vv != b[i]) {
if (w[par[vv]] == -1)
f = true;
if (w[par[vv]] != -1)
h = par[vv];
alo.push_back (par[vv]);
vv = a[par[vv]] ^ b[par[vv]] ^ vv;
}
if (!f)
continue;
if (h != -1) {
st.insert(i);
st.erase (vv);
int o = askt();
o = o - (k - w[vv]);
st.insert (vv);
for (int few : alo) {
if (w[few] == -1) {
st.erase (few);
w[few] = k - (askt() - o);
st.insert (few);
}
}
st.erase(i);
} else {
st.insert (i);
int mx = k;
vector <int> what;
for (int few : alo) {
st.erase (few);
int wef = askt();
mx = max (mx, wef);
what.push_back(wef);
st.insert (few);
}
st.erase (i);
for (int j = 0; j < (int)alo.size(); j++) {
w[alo[j]] = mx - what[j];
}
}
}
}
for (int i : tree) {
if (w[i] == -1)
w[i] = 1;
}
for (int i = 0; i < n; i++) {
vector <int> adj;
for (pair <int, int> p : g[i])
adj.push_back (p.S);
d[i] = askj (adj);
}
assert (false);
vector <int> ans;
for (int i = 0; i < n - 1; i++) {
int x = -1;
for (int j = 0; j < n; j++) {
if (d[j] == 1) {
x = j;
}
}
assert (x != -1);
vector <int> adj;
for (pair <int, int> p : g[x]) {
if (!ff[p.S])
adj.push_back (p.S);
}
int l = -1, r = (int)adj.size() - 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
vector <int> wef;
for (int j = 0; j <= mid; j++) {
wef.push_back(adj[j]);
}
if (askj(wef) == 1) {
r = mid;
} else {
l = mid;
}
}
ff[adj[r]] = true;
ans.push_back (adj[r]);
d[a[adj[r]]]--;
d[b[adj[r]]]--;
}
for (int x : ans)
cout << x << ' ';
cout << '\n';
if (count_common_roads (ans) != n - 1)
assert (false);
return ans;
}
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:2:
simurgh.cpp: In function 'int askj(std::vector<int>)':
simurgh.cpp:83:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
83 | assert (wef.size() == nn - 1);
| ~~~~~~~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
