#include <bits/stdc++.h>
#include "simurgh.h"
#define all(x) (x).begin(),(x).end()
using namespace std;
//#define ask count_common_roads
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 500;
vector<pii> g[nmax];
vector<int> occ;
vector<int> candr;
int flag;
int cnt = 0;
int ask(vector<int> r) {
return count_common_roads(r);
}
void dfs(int x) {
occ[x] = flag;
for(auto [y, ptr] : g[x]) {
if(occ[y] != 0) continue;
//cerr << x << ' ' << y << '\t' << ptr << '\n';
occ[y] = flag;
candr.emplace_back(ptr);
dfs(y);
}
return;
}
int mat[nmax][nmax];
vector<int> isgood;
vector<int> checked;
void solvefori(int i) {
fill(all(occ), 0);
candr.clear();
occ[i] = -1;
vector<vector<int>> atrs;
atrs.emplace_back();
vector<int> nv;
flag = 0;
for(auto [x, ptr] : g[i]) {
if(occ[x] == 0) {
flag++;
dfs(x);
nv.emplace_back(ptr);
atrs.emplace_back();
atrs.back().emplace_back(ptr);
}
else
atrs[occ[x]].emplace_back(ptr);
}
int startmn = sz(candr) - 1;
copy(all(nv), back_inserter(candr));
for(int i = 1; i <= flag; i++) {
//cerr << "--\n";
vector<int> rez;
int mx = -1;
for(int j = 0; j < sz(atrs[i]); j++) {
int u = atrs[i][j];
candr[startmn + i] = u;
if(checked[u] && isgood[u]) { mx = ask(candr); break; }
}
for(int j = 0; j < sz(atrs[i]); j++) {
int u = atrs[i][j];
candr[startmn + i] = u;
if(!checked[u])
rez.emplace_back(ask(candr));
else
rez.emplace_back(-1);
}
if(mx == -1)
mx = *max_element(all(rez));
for(int j = 0; j < sz(atrs[i]); j++) {
checked[atrs[i][j]] = 1;
if(rez[j] == mx)
isgood[atrs[i][j]] = 1;
}
}
}
vector<int> S4(int n, vector<int> u, vector<int> v) {
for(int i = 0; i < sz(u); i++) {
mat[u[i]][v[i]] = i;
mat[v[i]][u[i]] = i;
g[u[i]].emplace_back(v[i], i);
g[v[i]].emplace_back(u[i], i);
}
//cerr << "yura\n";
solvefori(0);
for(int j = 1; j < n; j++) checked[mat[i][0]] = 1;
for(int i = 1; i < n; i++) {
vector<int> crr;
for(int j = 0; j < n; j++) {
if(j == i) continue;
crr.emplace_back(mat[i][j]);
}
int totaltf = ask(crr);
for(int j = 0; j < i; j++)
totaltf -= isgood[mat[i][j]];
for(int smth = 0; smth < totaltf; smth++) {
auto trywith = [&](int lim) {
vector<int> ntwr;
ntwr.emplace_back(mat[0][i]);
int expected = isgood[mat[0][i]];
for(int j = 1; j <= lim; j++) {
if(j == i) continue;
ntwr.emplace_back(mat[i][j]);
if(checked[mat[i][j]]) expected += isgood[mat[i][j]];
}
for(int j = lim + 1; j < n; j++) {
if(j == i) continue;
ntwr.emplace_back(mat[0][j]);
if(checked[mat[i][j]]) expected += isgood[mat[i][j]];
}
return ask(ntwr) - expected;
};
int lim = 0;
for(int i = 9; i >= 0; i--) {
if(lim + (1 << i) >= n) continue;
if(trywith(lim + (1 << i)) <= smth) lim += (1 << i);
}
lim++;
checked[mat[i][lim]] = 1;
isgood[mat[i][lim]] = 1;
}
for(int j = 0; j < n; j++) {
if(j == i) continue;
checked[mat[i][j]] = 1;
}
}
vector<int> lst;
for(int i = 0; i < sz(isgood); i++)
if(isgood[i])
lst.emplace_back(i);
return lst;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
isgood.resize(sz(u));
checked.resize(sz(u));
occ.resize(n);
if(n > 240)
return S4(n, u, v);
for(int i = 0; i < sz(u); i++) {
g[u[i]].emplace_back(v[i], i);
g[v[i]].emplace_back(u[i], i);
}
for(int i = 0; i < n; i++) {
solvefori(i);
}
vector<int> lst;
for(int i = 0; i < sz(isgood); i++)
if(isgood[i])
lst.emplace_back(i);
//for(auto x : lst)
//cerr << x << ' ';
//cerr << '\n';
return lst;
}
/**
Anul asta se da centroid.
-- Surse oficiale
*/
Compilation message
simurgh.cpp: In function 'std::vector<int> S4(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:107:42: error: 'i' was not declared in this scope
107 | for(int j = 1; j < n; j++) checked[mat[i][0]] = 1;
| ^
