#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int n;
int id[maxn][maxn];
vector<int> adj[maxn];
bool a[maxn][maxn];
int gold[maxn][maxn], state[maxn];
int fa[maxn];
int goldcnt;
void edge(int u, int v, bool x) {
a[min(u, v)][max(u, v)] = x;
}
int qry() {
vector<int> ask;
int ret = 0;
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) if (a[i][j]) {
ask.push_back(id[i][j]);
ret -= (gold[i][j] == 1);
}
// for (int i:ask) cout << i << " "; cout << endl;
return ret + count_common_roads(ask);
}
vector<int> nodes;
bool vis[maxn];
void dfs0(int u) {
vis[u] = true, nodes.push_back(u);
for (int v:adj[u]) if (!vis[v] && state[v] <= 0) {
edge(u, v, 1);
dfs0(v);
}
}
void dfs1(int u) {
vis[u] = true;
for (int v:adj[u]) if (!vis[v] && state[v] <= 0) {
edge(u, v, 1);
dfs1(v);
}
}
void connect() {
for (int i=0;i<n;i++) if (state[i] == 1) dfs1(i);
}
void dfs2(int u) {
vis[u] = true;
for (int v:adj[u]) if (!vis[v] && !(state[v] == 0 && state[u] <= 0)) {
edge(u, v, 1);
fa[v] = u;
dfs2(v);
}
}
void addnode(int u) {
goldcnt++;
for (int i=0;i<n;i++) vis[i] = (state[i] == 1);
for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j] = (gold[i][j] == 1);
for (int i=0;i<n;i++) if (state[i] == 1) dfs2(i);
vector<int> cand;
for (int v:adj[u]) if (!state[v]) cand.push_back(v);
// cout << u << " " << cand.size() << endl;
// for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]) cout << i << " " << j << endl;
int init = qry();
for (int v:cand) {
edge(u, v, 1);
edge(v, fa[v], 0);
}
int val = qry();
for (int v:cand) {
edge(u, v, 1);
edge(v, fa[v], 0);
}
if (val == init) return;
vector<int> add;
for (int i=init + 1;i<=val;i++) {
int l = 0, r = cand.size()-1;
while (l < r) {
int mid = (l+r)/2;
for (int j=0;j<=mid;j++) {
int v = cand[v];
edge(u, v, 1);
edge(v, fa[v], 0);
}
int val = qry();
for (int j=0;j<=mid;j++) {
int v = cand[v];
edge(u, v, 1);
edge(v, fa[v], 0);
}
if (val >= i) r = mid;
else l = mid+1;
}
int v = cand[l];
add.push_back(v);
}
for (int v:add) {
fa[v] = u;
state[v] = 1;
gold[min(u, v)][max(u, v)] = 1;
}
for (int v:add) addnode(v);
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
n = N;
for (int i=0;i<n;i++) for (int j=0;j<n;j++) id[i][j] = -1, a[i][j] = 0, gold[i][j] = -1;
for (int i=0;i<U.size();i++) {
id[min(U[i], V[i])][max(U[i], V[i])] = i;
adj[U[i]].push_back(V[i]); adj[V[i]].push_back(U[i]);
}
for (int i=0;i<n;i++) state[i] = -1, fa[i] = -1;
state[0] = 1;
goldcnt = 1;
while (goldcnt < n) {
for (int i=0;i<n;i++) vis[i] = (state[i] == 1);
for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j] = (gold[i][j] == 1);
for (int i=0;i<n;i++) if (state[i] <= 0) {
nodes.clear();
dfs0(i);
break;
}
connect();
// cout << "edges\n";
// for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]) cout << i << " " << j << endl;
// cout << "nodes\n";
// for (int i:nodes) cout << i << " "; cout << endl;
vector<pair<int,int>> vec;
int mx = 0;
for (int u:nodes) if (state[u] == -1) {
vector<int> cand;
for (int v:adj[u]) if (state[v] == 1) cand.push_back(v);
if (!cand.size()) continue;
sort(cand.begin(), cand.end());
for (int v:cand) {
edge(u, v, 1);
if (v != cand[0]) edge(v, fa[v], 0);
}
int val = qry();
vec.push_back({u, val});
mx = max(val, mx);
for (int v:cand) {
edge(u, v, 0);
if (v != cand[0]) edge(v, fa[v], 1);
}
}
vector<pair<int,int>> add;
for (auto [u, val]:vec) {
vector<int> cand;
for (int v:adj[u]) if (state[v] == 1) cand.push_back(v);
sort(cand.begin(), cand.end());
if (val != mx) {
state[u] = 0;
fa[u] = cand[0];
} else {
int l = 0, r = cand.size() - 1;
while (l < r) {
int mid = (l+r+1)/2;
for (int i=0;i<=mid;i++) {
int v = cand[i];
edge(u, v, 1);
if (v != cand[0]) edge(v, fa[v], 0);
}
int val = qry();
for (int i=0;i<=mid;i++) {
int v = cand[i];
edge(u, v, 0);
if (v != cand[0]) edge(v, fa[v], 1);
}
if (val == mx) l = mid;
else r = mid-1;
}
int v = cand[l];
add.push_back({u, v});
}
}
for (auto [u, v]:add) {
state[u] = 1;
fa[u] = v;
gold[min(u, v)][max(u, v)] = 1;
}
for (auto [u, v]:add) addnode(u);
}
vector<int> ans;
for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (gold[i][j] == 1) {
ans.push_back(id[i][j]);
// cout << i << " " << j << " " << id[i][j] << endl;
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |