#include<bits/stdc++.h>
#include "simurgh.h"
#define MAXN 507
#define MAXM 300007
using namespace std;
int n,m,a[MAXM],b[MAXM],res[MAXM],t;
vector< pair<int,int> > vv[MAXN];
bool li[MAXN];
vector<int> tree,ask,g[MAXN],ans;
int curr,where[MAXN],maxres;
bool golden[MAXM],checked[MAXM];
void dfs(int x){
li[x]=true;
for(int i=0;i<vv[x].size();i++){
if(li[vv[x][i].first])continue;
tree.push_back(vv[x][i].second);
dfs(vv[x][i].first);
}
}
void comp(int x,int p,int id){
where[x]=id;
for(int i=0;i<g[x].size();i++){
if(g[x][i]==p)continue;
comp(g[x][i],x,id);
}
}
vector<int> find_roads(int N,vector<int> from,vector<int> to){
n=N; m=int(from.size());
for(int i=0;i<m;i++){
a[i]=from[i]; b[i]=to[i];
vv[a[i]].push_back({b[i],i});
vv[b[i]].push_back({a[i],i});
}
for(int i=0;i<200;i++){
for(int f=0;f<n;f++){
random_shuffle(vv[f].begin(),vv[f].end());
li[f]=false;
}
tree.clear(); dfs(rand()%n);
int r=rand()%tree.size();
for(int f=0;f<n;f++)g[f].clear();
ask.clear();
for(int f=0;f<n-1;f++){
if(f==r)continue;
ask.push_back(tree[f]);
g[a[tree[f]]].push_back(b[tree[f]]);
g[b[tree[f]]].push_back(a[tree[f]]);
}
comp(a[tree[r]],-1,1);
comp(b[tree[r]],-1,2);
maxres=-1;
for(int f=0;f<m;f++){
res[f]=0;
if(where[a[f]]!=where[b[f]]){
ask.push_back(f);
res[f]=count_common_roads(ask);
maxres=max(maxres,res[f]);
ask.pop_back();
}
}
for(int f=0;f<m;f++){
if(where[a[f]]!=where[b[f]] and res[f]==maxres){
golden[f]=true;
}
}
}
for(int i=0;i<m;i++){
if(golden[i]){
ans.push_back(i);
}
}
return ans;
}
Compilation message
simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i=0;i<vv[x].size();i++){
| ~^~~~~~~~~~~~~
simurgh.cpp: In function 'void comp(int, int, int)':
simurgh.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i=0;i<g[x].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
correct |
| 2 |
Correct |
1 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
340 KB |
correct |
| 4 |
Correct |
1 ms |
340 KB |
correct |
| 5 |
Correct |
1 ms |
340 KB |
correct |
| 6 |
Correct |
1 ms |
340 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
1 ms |
340 KB |
correct |
| 9 |
Correct |
1 ms |
340 KB |
correct |
| 10 |
Correct |
1 ms |
340 KB |
correct |
| 11 |
Correct |
1 ms |
340 KB |
correct |
| 12 |
Correct |
1 ms |
340 KB |
correct |
| 13 |
Correct |
1 ms |
340 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
correct |
| 2 |
Correct |
1 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
340 KB |
correct |
| 4 |
Correct |
1 ms |
340 KB |
correct |
| 5 |
Correct |
1 ms |
340 KB |
correct |
| 6 |
Correct |
1 ms |
340 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
1 ms |
340 KB |
correct |
| 9 |
Correct |
1 ms |
340 KB |
correct |
| 10 |
Correct |
1 ms |
340 KB |
correct |
| 11 |
Correct |
1 ms |
340 KB |
correct |
| 12 |
Correct |
1 ms |
340 KB |
correct |
| 13 |
Correct |
1 ms |
340 KB |
correct |
| 14 |
Incorrect |
28 ms |
340 KB |
WA in grader: NO |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
correct |
| 2 |
Correct |
1 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
340 KB |
correct |
| 4 |
Correct |
1 ms |
340 KB |
correct |
| 5 |
Correct |
1 ms |
340 KB |
correct |
| 6 |
Correct |
1 ms |
340 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
1 ms |
340 KB |
correct |
| 9 |
Correct |
1 ms |
340 KB |
correct |
| 10 |
Correct |
1 ms |
340 KB |
correct |
| 11 |
Correct |
1 ms |
340 KB |
correct |
| 12 |
Correct |
1 ms |
340 KB |
correct |
| 13 |
Correct |
1 ms |
340 KB |
correct |
| 14 |
Incorrect |
28 ms |
340 KB |
WA in grader: NO |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Correct |
1 ms |
340 KB |
correct |
| 3 |
Incorrect |
120 ms |
4384 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
correct |
| 2 |
Correct |
1 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
340 KB |
correct |
| 4 |
Correct |
1 ms |
340 KB |
correct |
| 5 |
Correct |
1 ms |
340 KB |
correct |
| 6 |
Correct |
1 ms |
340 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
1 ms |
340 KB |
correct |
| 9 |
Correct |
1 ms |
340 KB |
correct |
| 10 |
Correct |
1 ms |
340 KB |
correct |
| 11 |
Correct |
1 ms |
340 KB |
correct |
| 12 |
Correct |
1 ms |
340 KB |
correct |
| 13 |
Correct |
1 ms |
340 KB |
correct |
| 14 |
Incorrect |
28 ms |
340 KB |
WA in grader: NO |
| 15 |
Halted |
0 ms |
0 KB |
- |
