This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "simurgh.h"
#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
using namespace std;
typedef long long ll;
int n, m;
bitset<500> vis;
vector<int> tree;
list<int> adj[505];
map<pair<int, int>, int> mpp;
int get(int node1, int node2){
//cout << "get(" << node1 << ", " << node2 << ")" << endl;
if (mpp.count(mp(node2, node1)) == 0){
return mpp[mp(node1, node2)];
} else return mpp[mp(node2, node1)];
}
void findtree(int node, int ata){
//cout << "findtree(" << node << ", " << ata << ")" <<endl;
if (vis[node] == 1) return;
vis[node] = 1;
if (ata != -1){
tree.pb(get(node, ata));
}
for (list<int>::iterator it = adj[node].begin(); it != adj[node].end(); ++it){
findtree(*it, node);
}
}
vector<int> find_roads(int N, vector<int> u, vector<int> v) {
n = N;
set<int> ans;
for (int i = 0; i < u.size(); i++){
adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
mpp[mp(u[i], v[i])] = i;
}
for (int i = 0; i < n-1; i++){
vis.reset();
vis[i] = 1;
tree.clear();
findtree(i+1, -1);
//cout << "tree bitti" << endl;
vector<pair<int, int> > vals;
int maxx = 0;
tree.pb(0);
for (list<int>::iterator it = adj[i].begin(); it != adj[i].end(); ++it){
tree[n-2] = get(i, *it);
int val = count_common_roads(tree);
maxx = max(maxx, val);
vals.pb(mp(val, *it));
}
for (int j = 0; j < vals.size(); j++){
if (vals[j].first == maxx) ans.insert(get(i, vals[j].second));
}
}
vector<int> ansv;
for (set<int>::iterator it = ans.begin(); it != ans.end(); ++it){
ansv.pb(*it);
}
return ansv;
}
Compilation message (stderr)
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < u.size(); i++){
~~^~~~~~~~~~
simurgh.cpp:60:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vals.size(); j++){
~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |