#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int maxn = 550;
const int maxm = maxn*maxn/2;
int n, m, h[maxn], mark[maxn], U[maxm], V[maxm];
pair<int,int> low[maxn];
vector<int> g[maxn], span, ins, outs;
int par[maxn], pari[maxn], is_span[maxm];
int in[maxm], out[maxm];
int queryspan;
int ds[maxn], dsz[maxn];
int find(int v) {
if(v == ds[v]) return v;
return ds[v] = find(ds[v]);
}
void join(int u, int v) {
if(dsz[u] < dsz[v]) swap(u,v);
dsz[u]+= dsz[v];
ds[v] = u;
}
vector<int> construct(vector<int> edges) {
vector<int> finaledges;
for(int i = 0; i < n; i++) {
ds[i] = i;
dsz[i] = 1;
}
for(auto i : edges) {
int u = find(U[i]);
int v = find(V[i]);
if(u != v) {
join(u,v);
finaledges.pb(i);
}
}
assert(finaledges.size()==n-1);
return finaledges;
}
void dfslow(int u, int ant) {
mark[u] = 1;
low[u] = mp(h[u],-1);
for(auto i : g[u]) {
int v = U[i]+V[i]-u;
if(v == ant) continue;
if(!mark[v]) {
h[v] = h[u]+1;
par[v] = u;
pari[v] = i;
span.pb(i);
is_span[i] = 1;
dfslow(v,u);
low[u] = min(low[u],low[v]);
}
else {
low[u] = min(low[u],mp(h[v],i));
}
}
}
void dfs(int u, int ant) {
for(auto i : g[u]) {
int v = U[i]+V[i]-u;
if(v == ant || is_span[i] == 0) continue;
dfs(v,u);
}
if(u == 0 || in[pari[u]] || out[pari[u]]) return;
if(low[u] == mp(h[u],-1)) {
in[pari[u]] = 1;
ins.pb(pari[u]);
}
else {
int ilow = low[u].sc;
int ulow = U[ilow];
int vlow = V[ilow];
if(h[ulow] > h[vlow]) swap(ulow,vlow);
int v = vlow;
vector<int> edges;
while(v != ulow) {
edges.pb(pari[v]);
v = par[v];
}
int know = -1;
for(auto i : edges) {
if(in[i] || out[i]) {
know = i;
}
}
// cout << u << " " << ilow << " - " << count_common_roads(construct(span)) << endl;
if(know == -1) {
vector<pair<int,int>> cons;
cons.pb(mp(queryspan,ilow));
for(auto i : edges) {
vector<int> doquery;
for(auto j : span) {
if(j != i) doquery.pb(j);
}
doquery.pb(ilow);
cons.pb(mp(count_common_roads(construct(doquery)),i));
}
sort(all(cons));
if(cons[0].fr == cons.back().fr) {
// todo mundo out / 0
out[ilow] = 1; outs.pb(ilow);
for(auto i : edges) {
out[i] = 1; outs.pb(i);
}
}
else {
for(auto X : cons) {
int i = X.sc;
if(X.fr < cons.back().fr) {
// in / 1
in[i] = 1; ins.pb(i);
}
else {
// out / 0
out[i] = 1; outs.pb(i);
}
}
}
}
else {
vector<pair<int,int>> cons;
cons.pb(mp(queryspan,ilow));
vector<int> doquery;
for(auto i : edges) {
if(i != pari[u]) {
doquery.pb(i);
}
}
doquery.pb(ilow);
cons.pb(mp(count_common_roads(construct(doquery)),pari[u]));
doquery.clear();
for(auto i : edges) {
if(i != know) {
doquery.pb(i);
}
}
doquery.pb(ilow);
cons.pb(mp(count_common_roads(construct(doquery)),know));
doquery.clear();
if(in[know]) {
if(cons[0].fr == cons[2].fr) {
in[ilow] = 1; ins.pb(ilow);
}
else {
out[ilow] = 1; outs.pb(ilow);
}
if(cons[1].fr == cons[2].fr) {
in[pari[u]] = 1; ins.pb(pari[u]);
}
else {
out[pari[u]] = 1; outs.pb(pari[u]);
}
}
else {
if(cons[0].fr == cons[2].fr) {
out[ilow] = 1; outs.pb(ilow);
}
else {
in[ilow] = 1; ins.pb(ilow);
}
if(cons[1].fr == cons[2].fr) {
out[pari[u]] = 1; outs.pb(pari[u]);
}
else {
in[pari[u]] = 1; ins.pb(pari[u]);
}
}
}
}
}
vector<int> find_roads(int N, std::vector<int> UU, std::vector<int> VV) {
n = N;
m = UU.size();
for(int i = 0; i < m; i++) {
U[i] = UU[i];
V[i] = VV[i];
g[U[i]].pb(i);
g[V[i]].pb(i);
}
par[0] = -1;
pari[0] = -1;
dfslow(0,-1);
queryspan = count_common_roads(construct(span));
dfs(0,-1);
for(int u = 0; u < n; u++) {
int L = 0;
while(L < g[u].size()) {
int l = L;
int r = (int) g[u].size()-1;
int nx = -1;
while(l <= r) {
int mid = (l+r)>>1;
vector<int> doquery;
for(int i = 0; i <= mid; i++) doquery.pb(g[u][i]);
for(auto i : span) doquery.pb(i);
vector<int> used = construct(doquery);
int should = 0;
for(auto i : used) should+= in[i];
if(count_common_roads(used) > should) {
nx = mid;
r = mid-1;
}
else {
l = mid+1;
}
}
if(nx == -1) break;
in[g[u][nx]] = 1; ins.pb(g[u][nx]);
L = nx+1;
}
}
assert(ins.size() >= n-1);
assert(count_common_roads(ins) == n-1);
return ins;
for(auto i : span) {
cout << i << " " << in[i] << " " << out[i] << endl;
}
return vector<int>{0};
}
Compilation message
simurgh.cpp:49:2: error: extended character is not valid in an identifier
49 | assert(finaledges.size()==n-1);
| ^
simurgh.cpp: In function 'std::vector<int> construct(std::vector<int>)':
simurgh.cpp:49:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
49 | assert(finaledges.size()==n-1);
| ~~~~~~~~~~~~~~~~~^~~~~
simurgh.cpp:49:2: error: '\U000000a0assert' was not declared in this scope; did you mean 'assert'?
49 | assert(finaledges.size()==n-1);
| ^~~~~~~
| assert
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:219:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
219 | while(L < g[u].size()) {
| ~~^~~~~~~~~~~~~
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:3:
simurgh.cpp:248:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
248 | assert(ins.size() >= n-1);
| ~~~~~~~~~~~^~~~~~
