#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,msh[200009],E,BO[200009],ans[200009],Q[200009],QI,W[200009],WI,p[200009],pi,dep[200009],O[503][503],st,bo[200009],lef,rig,mid,cnt;
pair <int, int> P[200009];
vector <int> v[200009],xe,vv[200009],VV,V;
int fnd(int q){
if(msh[q]==0) return q; else return msh[q]=fnd(msh[q]);
}
bool mrg(int q, int w){
q=fnd(q);w=fnd(w);
if(q==w) return 0;
msh[q]=w;
return 1;
}
void dfs(int q, int w){
msh[q]=w;dep[q]=dep[w]+1;
for(vector <int>::iterator it=vv[q].begin(); it!=vv[q].end(); it++){
if((*it)==w) continue;
dfs((*it),q);
}
}
vector <int> tofull(vector <int> q){
vector <int> Q=q;
cnt++;
for(int h=0; h<q.size(); h++){
int we=0;
if(P[q[h]].first==i) we=P[q[h]].second; else we=P[q[h]].first;
int qw=O[we][msh[we]];bo[qw]=cnt;
}
for(int h=0; h<xe.size(); h++){
if(bo[xe[h]]!=cnt){
Q.push_back(xe[h]);
}
}
return Q;
}
vector<int> find_roads(int Nn, std::vector<int> Uu, std::vector<int> Vv) {
//int common = count_common_roads(r);
a=Nn;b=Uu.size();
for(i=0; i<Uu.size(); i++){
P[i]={Uu[i]+1,Vv[i]+1};
v[P[i].first].push_back(P[i].second);v[P[i].second].push_back(P[i].first);
O[P[i].first][P[i].second]=O[P[i].second][P[i].first]=i;
}
for(i=0; i<b; i++){
E=mrg(P[i].first,P[i].second);
if(E==1){
xe.push_back(i);BO[i]=1;
vv[P[i].first].push_back(P[i].second);vv[P[i].second].push_back(P[i].first);
}
}
st=count_common_roads(xe);
for(i=0; i<b; i++) ans[i]=2;
dfs(1,0);
for(ii=0; ii<b; ii++){
if(BO[ii]==0){
QI=0;WI=0;pi=0;
c=P[ii].first;d=P[ii].second;
while(c!=d){
if(dep[c]>=dep[d]){
QI++;Q[QI]=c;c=msh[c];
}else{
WI++;W[WI]=d;d=msh[d];
}
}
QI++;Q[QI]=c;
for(i=1; i<=QI; i++){
pi++;p[pi]=Q[i];
}
for(i=WI; i>=1; i--){
pi++;p[pi]=W[i];
}
QI=0;
for(i=1; i<pi; i++){
c=O[p[i]][p[i+1]];
if(ans[c]==2){
QI++;Q[QI]=c;
}
}
if(QI==0) continue;
E=0;
for(i=1; i<pi; i++){
c=O[p[i]][p[i+1]];
if(ans[c]!=2){
QI++;Q[QI]=c;E=ans[c];break;
}
}
if(QI==0){
QI++;Q[QI]=O[p[1]][p[2]];
}
WI=0;
for(i=1; i<=QI; i++){
VV.clear();
for(j=0; j<xe.size(); j++){
if(xe[j]!=Q[i]){
VV.push_back(xe[j]);
}
}
VV.push_back(ii);
WI++;W[WI]=count_common_roads(VV);
}
WI++;W[WI]=st;zx=0;xc=a+4;Q[WI]=ii;
for(i=1; i<=WI; i++){
zx=max(zx,W[i]);xc=min(xc,W[i]);
}
for(i=1; i<=WI; i++){
if(zx==xc){
ans[Q[i]]=E;
//cout<<Q[i]<<" "<<E<<"\n";
continue;
}
if(W[i]==zx){
//cout<<Q[i]<<" 0\n";
ans[Q[i]]=0;
}else{
//cout<<Q[i]<<" 1\n";
ans[Q[i]]=1;
}
}
}
}
for(ii=0; ii<b; ii++){
if(BO[ii]==1){
if(ans[ii]==2) ans[ii]=1;
}
}
/*for(ii=0; ii<b; ii++){
cout<<ans[ii]<<" ";
}
cout<<"\n";*/
for(ii=1; ii<=a; ii++){
dfs(ii,0);VV.clear();V.clear();
for(vector <int>::iterator it=v[ii].begin(); it!=v[ii].end(); it++){
c=O[ii][(*it)];
if(ans[c]!=2) continue;
VV.push_back(c);
}
if(VV.size()==0) continue;
V=tofull(VV);
zx=count_common_roads(V);
for(int h=0; h<V.size(); h++){
if(ans[V[h]]==1) zx--;
}
//cout<<ii-1<<" "<<zx<<"\n";
E=-1;
while(zx>0){
lef=E;rig=VV.size();
while(1){
if(lef+1>=rig) break;
mid=(lef+rig)/2;
V.clear();
for(int h=E+1; h<=mid; h++){
V.push_back(VV[h]);
}
V=tofull(V);
c=count_common_roads(V);
//cout<<"c: "<<c<<" "<<ii<<" "<<lef<<" "<<mid<<" "<<rig<<"\n";
for(int h=0; h<V.size(); h++){
if(ans[V[h]]==1) c--;
}
//cout<<"c: "<<c<<" "<<ii<<" "<<lef<<" "<<mid<<" "<<rig<<"\n";
if(c>0){
rig=mid;
}else{
lef=mid;
}
}
/*if(rig==VV.size()){
cout<<"PANIC";exit(0);
}*/
for(int h=E+1; h<rig; h++) ans[VV[h]]=0;
ans[VV[rig]]=1;
zx--;
}
}
VV.clear();
for(ii=0; ii<b; ii++){
if(ans[ii]==1) VV.push_back(ii);
}
return VV;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> tofull(std::vector<int>)':
simurgh.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int h=0; h<q.size(); h++){
| ~^~~~~~~~~
simurgh.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int h=0; h<xe.size(); h++){
| ~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:41:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(i=0; i<Uu.size(); i++){
| ~^~~~~~~~~~
simurgh.cpp:95:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(j=0; j<xe.size(); j++){
| ~^~~~~~~~~~
simurgh.cpp:142:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(int h=0; h<V.size(); h++){
| ~^~~~~~~~~
simurgh.cpp:159:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for(int h=0; h<V.size(); h++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9684 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9684 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9684 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9684 KB |
correct |
| 2 |
Incorrect |
6 ms |
9684 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9684 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
