#include "simurgh.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define nxt first
#define idx second
#define ff first
#define ss second
using namespace std;
int nodes, edjes;
vector<pair<int, int> >adj[501];
vector<pair<int, int > >ejes;
vector<int>indicesAns, otros;
int hoja;
bool yaSeSabia[500*500];
bool checked[501];
int contC = 0;
int repre[501];
int ultimoEje;
//bool vis[501];
void memss(){
//for(int i = 0 ; i < nodes; i ++)vis[i] = false;
}
int findd(int nod){
if(repre[nod] == nod)return nod;
return repre[nod] = findd(repre[nod]);
}
void joinn(int a, int b){
a = findd (a);
b = findd (b);
if(a==b)return;
repre[a] = b;
}
void unir(){
//cout << " nuevo arbol " << endl;
otros.clear();
hoja = -1;
for(int i = 0 ; i < nodes ; i ++)repre[i] = i;
for(int i = 0 ; i < indicesAns.size() ; i ++){
joinn(ejes[indicesAns[i]].ff, ejes[indicesAns[i]].ss);
//cout << ejes[indicesAns[i]].ff << " join " << ejes[indicesAns[i]].ss << endl;
}
ultimoEje = -1;
for(int i = 0 ; i < edjes ; i ++){
if(findd (ejes[i].ff) != findd(ejes[i].ss)){
otros.pb(i);
ultimoEje = i;
joinn(ejes[i].ff, ejes[i].ss);
//cout << ejes[i].ff << " join " << ejes[i].ss << endl;
hoja = ejes[i].ss;
}
}
}
int calculate(vector<pair<int, int> >&resp){
int k = hoja;
checked[k] = true;
//cout << "probando para " << k << endl;
vector<int>indTest;
indTest = indicesAns;
if(ultimoEje == -1)return -1;
for(auto i : otros)if(i != ultimoEje)indTest.pb(i);
indTest.pb(ultimoEje);
int maxi = INT_MIN;
resp.pb({ultimoEje, count_common_roads(indTest)});
yaSeSabia[ultimoEje] = true;
maxi = max(maxi, resp.back().ss);
for(int i = 0 ; i < adj[k].size() ; i ++){
if(yaSeSabia[adj[k][i].idx])continue;
indTest.pop_back();
indTest.pb(adj[k][i].idx);
yaSeSabia[adj[k][i].idx] = true;
resp.pb({adj[k][i].idx, count_common_roads( indTest )});
maxi = max(maxi, resp.back().ss);
}
return maxi;// Ya calcule si estos ejes son o no de la respuesta.
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
for(int i = 0 ; i < n; i ++)checked[i] = false;
for(int i = 0 ; i < u.size() ; i ++){
yaSeSabia[i] = false;
}
nodes = n;
edjes = u.size();
for(int i = 0 ; i < edjes ; i ++){
adj[u[i]].pb({v[i], i});
adj[v[i]].pb({u[i], i});
ejes.pb({u[i], v[i]});
}
memss();
while(contC < n){
unir();
vector<pair<int, int> >resp;
int maxi = calculate(resp);
if(maxi == -1)break;
//cout << " gold " << endl;
for(auto i : resp){
if(i.ss == maxi){
//cout << i.ff << endl;
indicesAns.pb(i.ff);
}
}
if(indicesAns.size() == n-1)return indicesAns;
}
return indicesAns;
}
Compilation message
simurgh.cpp: In function 'void unir()':
simurgh.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 0 ; i < indicesAns.size() ; i ++){
| ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'int calculate(std::vector<std::pair<int, int> >&)':
simurgh.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0 ; i < adj[k].size() ; i ++){
| ~~^~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i = 0 ; i < u.size() ; i ++){
| ~~^~~~~~~~~~
simurgh.cpp:111:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
111 | if(indicesAns.size() == n-1)return indicesAns;
| ~~~~~~~~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
