#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
struct Edge {
int a,idx,mode;
};
int n,m,deg[505];
vector<pii> edge;
priority_queue<pii> pq; //deg, node
vector<Edge> adj[505];
bool fin[505],ans[250010];
int p[505],r[505];
void reset() {
for (int i=0; i<n; ++i) p[i]=i, r[i]=1;
}
int find(int x) {
while (x!=p[x]) x=p[x];
return x;
}
void unite(int x, int y) {
x=find(x); y=find(y);
if (r[x]<r[y]) swap(x,y);
p[y]=x;
if (r[x]==r[y]) ++r[x];
}
void solve1(int x) {
vector<pii> temp; //val,idx
vector<int> v;
int ma=0;
reset();
for (int i=0; i<m; ++i) {
if (edge[i].first==x || edge[i].second==x) continue;
if (find(edge[i].first)!=find(edge[i].second)) {
unite(edge[i].first,edge[i].second);
v.push_back(i);
}
}
for (auto s : adj[x]) {
v.push_back(s.idx);
int h=count_common_roads(v);
ma=max(h,ma);
temp.push_back(pii(h,s.idx));
v.pop_back();
}
for (auto s : temp) if (s.first==ma) ans[s.second]=true;
}
vector<int> find_roads(int N, vector<int> u, vector<int> v) {
n=N;
m=u.size();
for (int i=0; i<m; ++i) {
edge.push_back(pii(u[i],v[i]));
adj[u[i]].push_back({v[i],i,-1});
adj[v[i]].push_back({u[i],i,-1});
++deg[u[i]];
++deg[v[i]];
}
int ma=0, st;
for (int i=0; i<n; ++i) if (deg[i]>ma) ma=deg[i], st=i;
for (int i=0; i<n; ++i) solve1(i);
vector<int> Ans;
for (int i=0; i<m; ++i) if (ans[i]) Ans.push_back(i);
return Ans;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:71:12: warning: variable 'st' set but not used [-Wunused-but-set-variable]
71 | int ma=0, st;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
0 ms |
212 KB |
correct |
| 6 |
Correct |
0 ms |
212 KB |
correct |
| 7 |
Correct |
1 ms |
212 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Incorrect |
0 ms |
212 KB |
WA in grader: NO |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
0 ms |
212 KB |
correct |
| 6 |
Correct |
0 ms |
212 KB |
correct |
| 7 |
Correct |
1 ms |
212 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Incorrect |
0 ms |
212 KB |
WA in grader: NO |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
0 ms |
212 KB |
correct |
| 6 |
Correct |
0 ms |
212 KB |
correct |
| 7 |
Correct |
1 ms |
212 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Incorrect |
0 ms |
212 KB |
WA in grader: NO |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Incorrect |
114 ms |
5296 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
0 ms |
212 KB |
correct |
| 6 |
Correct |
0 ms |
212 KB |
correct |
| 7 |
Correct |
1 ms |
212 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Incorrect |
0 ms |
212 KB |
WA in grader: NO |
| 10 |
Halted |
0 ms |
0 KB |
- |
