#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
// int count_common_roads(vector<int> vec)
const int maxn = 505;
const int maxm = maxn*maxn/2;
int n, m;
int edgeID[maxn][maxn];
vector<int> U, V;
vector<int> adj[maxn];
int par[maxn];
bool vis[maxn];
int dep[maxn];
int tree_score[maxm];
bool isInTree[maxm];
bool isNotBridge[maxm];
bool res[maxm];
vector<int> backedges;
vector<int> output;
void find_tree(int u = 0, int p = -1)
{
if(p != -1) par[u] = p;
vis[u] = true;
for(auto v : adj[u])
{
if(!vis[v])
{
dep[v] = dep[u]+1;
find_tree(v, u);
isInTree[edgeID[u][v]] = true;
output.push_back(edgeID[u][v]);
}
else if(v != p)
{
backedges.pb(edgeID[u][v]);
}
}
}
bool cmp(int a, int b)
{
int ua = U[a], ub = U[b];
int va = V[a], vb = V[b];
return min(dep[ua], dep[va])< min(dep[ub], dep[vb]);
}
void delete_from_output(int u)
{
vector<int> nou;
for(auto x : output)
{
if(x == u) continue;
nou.pb(x);
}
output = nou;
}
void add_to_output(int u)
{
output.pb(u);
}
int ask()
{
return count_common_roads(output);
}
vector<int> find_roads(int _n, vector<int> _u, vector<int> _v)
{
memset(tree_score, -1, sizeof tree_score);
n = _n; m = _u.size();
U = _u; V = _v;
for(int i = 0; i< m; i++)
{
int u = U[i], v = V[i];
edgeID[u][v] = edgeID[v][u] = i;
adj[u].pb(v); adj[v].pb(u);
}
dep[0] = 1; find_tree();
sort(backedges.begin(), backedges.end());
backedges.resize(unique(backedges.begin(), backedges.end())-backedges.begin());
sort(backedges.begin(), backedges.end(), cmp);
int base_score = ask();
for(auto edge : backedges)
{
int u = U[edge], v = V[edge];
if(dep[u]< dep[v]) swap(u, v);
int cur = u;
int sample = -1;
bool not_asked = true;
while(cur != v)
{
int tp = par[cur];
int id = edgeID[cur][tp];
if(tree_score[id] != -1)
{
not_asked = false;
sample = id;
}
cur = tp;
}
if(not_asked)
{
cur = u;
add_to_output(edge);
int mn = base_score, mx = base_score;
while(cur != v)
{
int tp = par[cur];
int id = edgeID[cur][tp];
isNotBridge[id] = true;
delete_from_output(id);
tree_score[id] = ask();
mn = min(tree_score[id], mn);
mx = max(tree_score[id], mx);
add_to_output(id);
cur = tp;
}
delete_from_output(edge);
cur = u;
while(cur != v)
{
int tp = par[cur];
int id = edgeID[cur][tp];
if(mn == mx) res[id] = false;
else if(tree_score[id] == mn) res[id] = true;
else res[id] = false;
cur = tp;
}
if(mn != mx && base_score == mn) res[edge] = true;
}
else
{
delete_from_output(sample);
add_to_output(edge);
int mod_score = _score-res[sample];
int temp = ask();
if(temp> mod_score) res[edge] = true;
else res[edge] = false;
add_to_output(sample);
cur = u;
while(cur != v)
{
int tp = par[cur];
int id = edgeID[cur][tp];
if(tree_score[edge] != -1)
{
cur = tp; continue;
}
delete_from_output(id);
int temp = ask();
int mod_score = base_score+res[edge];
if(temp< mod_score) res[id] = true;
else res[id] = false;
add_to_output(id);
cur = tp;
}
delete_from_output(edge);
}
}
output.clear();
for(int i = 0; i< m; i++)
{
if((!isNotBridge[i] and isInTree[i]) or res[i]) output.pb(i);
}
assert(ask() == n-1);
return output;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:152:20: error: '_score' was not declared in this scope
int mod_score = _score-res[sample];
^~~~~~
simurgh.cpp:152:20: note: suggested alternative: 'mod_score'
int mod_score = _score-res[sample];
^~~~~~
mod_score
