#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
bool uu[125255];
int h[505],bs[505],par[505],tp,a,b,cur,tpans,nw;
vector<int>vv[505];
int F(int N)
{
if(bs[N]==N)return N;
else return bs[N]=F(bs[N]);
}
void un(int X,int Y)
{
bs[F(X)]=F(Y);
return;
}
void dfs(int N,int pr,int H)
{
bs[N]=pr;
h[N]=H;
for(int i=0;i<vv[N].size();i++)
{
if(vv[N][i]==pr)continue;
dfs(vv[N][i],N,H+1);
}
return;
}
vector<int> find_roads(int n,vector<int>u,vector<int>v)
{
vector<int>ryl;
vector<int>ans;
for(int i=0;i<n;i++)bs[i]=i;
for(int i=0;i<u.size();i++)
{
uu[i]=false;
// printf("%d %d\n",F(u[i]),F(v[i]));
if(F(u[i])==F(v[i]))continue;
un(u[i],v[i]);
// printf("[%d]",i);
ans.pb(i);
ryl.pb(0);
uu[i]=true;
}
tp=count_common_roads(ans);
for(int i=0;i<u.size();i++)
{
if(uu[i])continue;
a=u[i],b=v[i];
for(int i=0;i<n;i++)vv[i].clear();
for(int i=0;i<ans.size();i++)vv[u[ans[i]]].pb(v[ans[i]]),vv[v[ans[i]]].pb(u[ans[i]]);
dfs(1,-1,1);
if(h[a]<h[b])swap(a,b);
while(h[a]>h[b])
{
for(int i=0;i<ans.size();i++)
{
if((a==u[ans[i]]&&par[a]==v[ans[i]])||(par[a]==u[ans[i]]&&a==v[ans[i]]))cur=i;
}
a=par[a];
tpans=ans[cur];
ans[cur]=i;
nw=count_common_roads(ans);
if(nw>tp)break;
ans[cur]=tpans;
}
if(nw>tp)
{
tp=nw;
continue;
}
while(a!=b)
{
for(int i=0;i<ans.size();i++)
{
if((a==u[ans[i]]&&par[a]==v[ans[i]])||(par[a]==u[ans[i]]&&a==v[ans[i]]))cur=i;
}
a=par[a];
tpans=ans[cur];
ans[cur]=i;
nw=count_common_roads(ans);
if(nw>tp)break;
ans[cur]=tpans;
for(int i=0;i<ans.size();i++)
{
if((b==u[ans[i]]&&par[b]==v[ans[i]])||(par[b]==u[ans[i]]&&b==v[ans[i]]))cur=i;
}
b=par[b];
tpans=ans[cur];
ans[cur]=i;
nw=count_common_roads(ans);
if(nw>tp)break;
ans[cur]=tpans;
}
if(nw>tp)
{
tp=nw;
continue;
}
}
return ans;
}
Compilation message
simurgh.cpp: In function 'void dfs(int, int, int)':
simurgh.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0;i<vv[N].size();i++)
| ~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=0;i<u.size();i++)
| ~^~~~~~~~~
simurgh.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<u.size();i++)
| ~^~~~~~~~~
simurgh.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i=0;i<ans.size();i++)vv[u[ans[i]]].pb(v[ans[i]]),vv[v[ans[i]]].pb(u[ans[i]]);
| ~^~~~~~~~~~~
simurgh.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=0;i<ans.size();i++)
| ~^~~~~~~~~~~
simurgh.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i=0;i<ans.size();i++)
| ~^~~~~~~~~~~
simurgh.cpp:84:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=0;i<ans.size();i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
correct |
| 2 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
