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 "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> >adj[241];
vector<int>t;
bool vis[241], check[28800]={false};
void DFS(int u, int p){
vis[u]=true;
for(auto v:adj[u]){
if(v.first!=p && vis[v.first]==false){
vis[v.first]=true;
if(p!=-1) t.push_back(v.second);
DFS(v.first, u);
}
}
}
int calc(int u){
int mx=-1, p, tmp;
for(auto v:adj[u]){
if(check[v.second])continue;
t.push_back(v.second);
tmp=count_common_roads(t);;
if(tmp>mx){
mx=tmp;
p=v.second;
}
t.pop_back();
}
return p;
}
vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
int f, ind=0;
vector<int> res(n - 1);
for(int i=0; i<u.size(); i++){
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
for(int i=0; i<n; i++){
memset(vis, false, sizeof vis);
t.clear();
DFS(i, -1);
f=calc(i);
check[f]=true;
res[ind++]=f;
}
//for(int i=0; i<n-1; i++) cout << res[i] << " ";
return res;
}
Compilation message (stderr)
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<u.size(); i++){
~^~~~~~~~~
simurgh.cpp: In function 'int calc(int)':
simurgh.cpp:34:9: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
return p;
^
# | 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... |