#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN=500, mxM=mxN*(mxN-1)/2;
int n, tin[mxN], low[mxN], dt=1, b[mxM], bs, st[mxM], sth, t[mxN], p[mxN];
vector<int> eu, ev, adj[mxN], ans;
bool c[mxN];
//debug stuff
void pv(string s, vector<int> v) {
cout << s << endl;
for(int i : v)
cout << i << " ";
cout << endl;
}
void dfs1(int u=0, int p=-1) {
tin[u]=low[u]=dt++;
for(int e : adj[u]) {
int v=eu[e]^ev[e]^u;
if(!tin[v]) {
st[sth++]=e;
dfs1(v, u);
low[u]=min(low[v], low[u]);
if(low[u]>=tin[u]) {
do {
b[st[--sth]]=bs;
} while(st[sth]^e);
++bs;
}
} else if(tin[v]<tin[u]) {
st[sth++]=e;
low[u]=min(tin[v], low[u]);
}
}
}
int find(int x) {
return x^p[x]?p[x]=find(p[x]):x;
}
bool join(int x, int y) {
if((x=find(x))==(y=find(y)))
return 0;
p[x]=y;
return 1;
}
vector<int> fst(vector<int> w) {
vector<int> r;
iota(p, p+n, 0);
for(int i=0; i<eu.size(); ++i) {
//cout << "fst " << i << endl;
if(w[eu[i]]&&w[ev[i]]&&join(eu[i], ev[i]))
r.push_back(i);
}
return r;
}
void dc(vector<int> &a, vector<int> &b, vector<int> &c, int l, int r, int s1, int s2) {
if(s2==s1)
return;
if(l==r) {
c.push_back(b[l]);
return;
}
int m=(l+r)/2;
vector<int> d=a;
for(int i=l; i<=r; ++i)
d[i]=b[i];
int sl=count_common_roads(d);
dc(a, b, c, l, m, s1, sl);
dc(a, b, c, m+1, r, s1, s2-sl+s1);
}
void dfs2(int u=0) {
//cout << "d2 " << u << endl;
vector<int> v1, v2, r;
for(int e : adj[u]) {
int v=eu[e]^ev[e]^u;
if(c[v])
continue;
if(t[v]<0) {
v2.push_back(e);
t[v]=e;
} else
v1.push_back(e);
}
if(v1.size()) {
//pv("pv1", v1);
vector<int> w(n, 1);
for(int e : v1)
w[eu[e]^ev[e]^u]=0;
vector<int> s1=fst(w), s2=s1;
s2.insert(s2.begin(), v1.begin(), v1.end());
//pv("s1", s1);
//pv("s2", s2);
for(int i=0; i<v1.size(); ++i)
s1.insert(s1.begin()+i, t[eu[v1[i]]^ev[v1[i]]^u]);
dc(s1, v1, r, 0, v1.size()-1, count_common_roads(s1), count_common_roads(s2));
//pv("r", r);
}
if(v2.size()) {
//pv("pv2", v2);
vector<int> w(n, 1);
w[u]=0;
vector<int> s=fst(w);
//pv("s1", s);
for(int e : ans)
if(join(eu[e], ev[e]))
s.push_back(e);
for(int e : r)
if(join(eu[e], ev[e]))
s.push_back(e);
for(int e : adj[u])
if(join(eu[e], ev[e]))
s.push_back(e);
//pv("s2", s);
int bc=count_common_roads(s);
//cout << bc << endl;
sort(v2.begin(), v2.end(), [](const int &i, const int &j) {
return b[i]<b[j];
});
for(int i=0, j=0; i<v2.size(); ) {
//cout << "hi2 " << i << endl;
for(; j<v2.size()&&b[v2[j]]==b[v2[i]]; ++j);
int o;
for(int e : s)
if(b[e]==b[v2[i]])
o=e;
s.erase(find(s.begin(), s.end(), o));
//cout << "edge removed " << o << endl;
vector<int> a;
int cm=bc;
for(; i<j; ++i) {
s.push_back(v2[i]);
int cc=count_common_roads(s);
if(cc>cm) {
cm=cc;
a=vector<int>();
}
if(cc==cm)
a.push_back(v2[i]);
s.pop_back();
}
//cout << cm << endl;
//pv("on", a);
r.insert(r.end(), a.begin(), a.end());
s.push_back(o);
}
}
for(int e : r) {
ans.push_back(e);
c[eu[e]^ev[e]^u]=1;
}
for(int e : r)
dfs2(eu[e]^ev[e]^u);
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
::n=n;
eu=u;
ev=v;
for(int i=0; i<u.size(); ++i) {
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
}
dfs1();
c[0]=1;
memset(t, -1, 4*n);
dfs2();
return ans;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> fst(std::vector<int>)':
simurgh.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<eu.size(); ++i) {
~^~~~~~~~~~
simurgh.cpp: In function 'void dfs2(int)':
simurgh.cpp:99:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v1.size(); ++i)
~^~~~~~~~~~
simurgh.cpp:125:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0, j=0; i<v2.size(); ) {
~^~~~~~~~~~
simurgh.cpp:127:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; j<v2.size()&&b[v2[j]]==b[v2[i]]; ++j);
~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:165:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<u.size(); ++i) {
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
