#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 501;
int vis[N] , vi = 0;
vector< pair<int,int> > g[N], T[N];
vector< int > ans;
bool ok[N * N] = {0} , asked[N * N];
int comp[N];
void DFS(int node,int cant,int cur,vector<int> &v){
vis[node] = vi;
comp[node] = cur;
for(int i=0;i<g[node].size();i++){
if(g[node][i].first != cant && vis[g[node][i].first] != vi){
v.push_back(g[node][i].second);
DFS(g[node][i].first,cant,cur,v);
}
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
for(int i=0;i<u.size();i++){
g[u[i]].push_back(make_pair(v[i],i));
g[v[i]].push_back(make_pair(u[i],i));
}
for(int i=0;i<n;i++){
vi++;
int cnt = 0 ;
vector<int> tree, tree2 ;
for(int j=0;j<n;j++){
if(j == i) continue;
if(vis[j] != vi){
DFS(j,i,cnt++,tree2);
}
}
vector< pair<int,int> > v , v2;
for(int j=0;j<g[i].size();j++){
v.push_back(make_pair(comp[g[i][j].first],g[i][j].second));
}
sort(v.begin(),v.end());
int res = -1;
for(int k=0;k<v.size();k++){
if(k == 0 || v[k].first != v[k-1].first){
for(int j=0;j<v2.size();j++){
if(v2[j].first == res){
ok[v2[j].second] = true;
}
}
res = -1;
v2.clear();
bool taken[N] = {0};
tree.clear();
for(int j=0;j<g[i].size();j++){
if(!taken[comp[g[i][j].first]] && comp[g[i][j].first] != v[k].first){
taken[comp[g[i][j].first]] = true;
tree.push_back(g[i][j].second);
}
}
for(int i=0;i<tree2.size();i++) tree.push_back(tree2[i]);
}
if(asked[v[k].second]) continue;
asked[v[k].second] = true;
tree.push_back(v[k].second);
int cur = count_common_roads(tree);
tree.pop_back();
v2.push_back(make_pair(cur,v[k].second));
res = max(res,cur);
}
for(int j=0;j<v2.size();j++){
if(v2[j].first == res){
ok[v2[j].second] = true;
}
}
}
for(int i=0;i<u.size();i++) if(ok[i]) ans.push_back(i);
return ans;
}
Compilation message
simurgh.cpp: In function 'void DFS(int, int, int, std::vector<int>&)':
simurgh.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[node].size();i++){
^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<u.size();i++){
^
simurgh.cpp:39:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<g[i].size();j++){
^
simurgh.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<v.size();k++){
^
simurgh.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v2.size();j++){
^
simurgh.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<g[i].size();j++){
^
simurgh.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<tree2.size();i++) tree.push_back(tree2[i]);
^
simurgh.cpp:72:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v2.size();j++){
^
simurgh.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<u.size();i++) if(ok[i]) ans.push_back(i);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2544 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2544 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2544 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2544 KB |
correct |
| 2 |
Incorrect |
0 ms |
2544 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2544 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
