#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
vector<int>adj[maxn];
int n,m,vis[maxn],high[maxn],p[maxn];
pair<int,int>alle[maxn];
vector<int>dfsor;
map<pair<int,int>,int>lnk;
map<int,int>mp;
vector<int>res;
vector<int>adjt,updy;
struct dsu{
int par[maxn];
dsu(){
for(int i=0;i<maxn;i++){
par[i]=i;
}
}
int root(int u){
if(u==par[u]){
return u;
}
return par[u]=root(par[u]);
}
int con(int u,int v){
u=root(u);v=root(v);
if(u==v){
return 0;
}
par[u]=v;
return 1;
}
void clear(){
for(int i=0;i<maxn;i++){
par[i]=i;
}
}
}ds;
int pors(set<int>st){
vector<int>ers;
for(auto x:st){
ers.push_back(x);
}
return count_common_roads(ers);
}
bool check(vector<int>ch){
int ent=0;
set<int>ers;
for(auto x:ch){
ers.insert(x);
ds.con(alle[x].first,alle[x].second);
}
for(auto x:adjt){
if(ds.con(alle[x].first,alle[x].second)){
ent+=mp[x];
ers.insert(x);
}
}
if(ent==pors(ers)){
return 0;
}
return 1;
}
void upd(int ind){
//cout<<"tagh: "<<ind<<endl;
set<int>st;
for(auto x:adjt){
st.insert(x);
}
st.insert(ind);
vector<int>alli;
alli.push_back(ind);
int mx=-1;
int u=alle[ind].first,v=alle[ind].second;
if(high[u]>high[v]){
swap(u,v);
}
while(v!=u){
alli.push_back(lnk[make_pair(v,p[v])]);
v=p[v];
}
for(auto x:alli){
st.erase(x);
mx=max(mx,pors(st));
st.insert(x);
//cout<<"injy: "<<x<<" "<<mx<<endl;
}
for(auto x:alli){
if(mp.count(x)==1){
continue;
}
st.erase(x);
if(mx==pors(st)){
mp[x]=0;
}else{
mp[x]=1;
res.push_back(x);
}
st.insert(x);
}
}
pair<int,int>buildt(int u=0,int par=-1){
vis[u]=1;
p[u]=par;
pair<int,int>ret=make_pair(high[u],m);
for(auto x:adj[u]){
if(vis[x]==0){
high[x]=high[u]+1;
ret=min(ret,buildt(x,u));
adjt.push_back(lnk[make_pair(u,x)]);
}
}
for(auto x:adj[u]){
if(x!=par){
ret=min(ret,make_pair(high[x],lnk[make_pair(u,x)]));
}
}
if(u!=0){
if(mp.count(lnk[make_pair(u,par)])==1){
return ret;
}
if(ret.first>=high[u]){
res.push_back(lnk[make_pair(u,par)]);
}else{
updy.push_back(ret.second);
}
}
return ret;
}
void erasea(){
sort(adjt.begin(),adjt.end());
set<int>sth;
for(auto x:adjt){
sth.insert(x);
}
for(int i=0;i<n;i++){
vector<int>fake;
for(auto x:adj[i]){
if(mp.count(lnk[make_pair(i,x)])&&i<x){
fake.push_back(x);
}
}
swap(adj[i],fake);
}
}
void bagh(){
for(int i=0;i<n;i++){
int low=0;
while(low<(int)adj[i].size()){
int high=(int)adj[i].size(),mid;
while(high-low>=1){
mid=(high+low)>>1;
vector<int>ch;
for(int j=low;j<=mid;j++){
ch.push_back(lnk[make_pair(i,adj[i][j])]);
}
if(check(ch)){
high=mid;
}else{
low=mid+1;
}
}
if(high!=adj[i].size()){
res.push_back(lnk[make_pair(i,adj[i][high])]);
low=high+1;
}
}
}
}
vector<int>solve(){
buildt();
for(auto x:res){
//cout<<"magemishe "<<x<<endl;
}
for(auto x:updy){
upd(x);
}
for(auto x:adjt){
//cout<<"ha: "<<x<<endl;
}
for(auto x:res){
//cout<<"magemishe "<<x<<endl;
}
erasea();
bagh();
return res;
}
std::vector<int> find_roads(int n_, std::vector<int> u, std::vector<int> v){
m=(int)u.size();
for(int i=0;i<m;i++){
lnk[make_pair(u[i],v[i])]=lnk[make_pair(v[i],u[i])]=i;
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
alle[i]=make_pair(u[i],v[i]);
}
return solve();
}
Compilation message
simurgh.cpp: In function 'void bagh()':
simurgh.cpp:171:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | if(high!=adj[i].size()){
| ~~~~^~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> solve()':
simurgh.cpp:181:11: warning: unused variable 'x' [-Wunused-variable]
181 | for(auto x:res){
| ^
simurgh.cpp:187:11: warning: unused variable 'x' [-Wunused-variable]
187 | for(auto x:adjt){
| ^
simurgh.cpp:190:11: warning: unused variable 'x' [-Wunused-variable]
190 | for(auto x:res){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
correct |
| 2 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
