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[501];
vector<int>t;
vector<int> res;
bool vis[501], check[125000]={false};
int N;
void DFS(int u, int p){
vis[u]=true;
for(auto v:adj[u]){
if(v.first!=p && vis[v.first]==false){
if(p!=-1) t.push_back(v.second);
DFS(v.first, u);
}
}
}
int calc(int u){
vector<int>b;
int mx=-1, p=-1, tmp;
if(t.size()!=N-2) return -1;
for(auto v:adj[u]){
if(check[v.second]){
t.push_back(v.second);
mx=count_common_roads(t);
t.pop_back();
break;
}
}
for(auto v:adj[u]){
if(check[v.second])continue;
t.push_back(v.second);
tmp=count_common_roads(t);
if(mx==-1){
mx=tmp;
b.push_back(v.second);
p=v.second;
}
else if(tmp>mx){
b.clear();
mx=tmp;
b.push_back(v.second);
p=v.second;
}
else if(tmp==mx){
b.push_back(v.second);
p=v.second;
}
t.pop_back();
}
for(int i=0; i<b.size(); i++){
check[b[i]]=true;
res.push_back(b[i]);
}
return p;
}
vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N=n;
int f, ind=0;
memset(check, false, sizeof check);
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);
if(f<0 || f>u.size() || check[f]) continue;
}
res.resize(n-1);
return res;
}
Compilation message (stderr)
simurgh.cpp: In function 'int calc(int)':
simurgh.cpp:25:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(t.size()!=N-2) return -1;
~~~~~~~~^~~~~
simurgh.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<b.size(); i++){
~^~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<u.size(); i++){
~^~~~~~~~~
simurgh.cpp:75:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(f<0 || f>u.size() || check[f]) continue;
~^~~~~~~~~
simurgh.cpp:64:9: warning: unused variable 'ind' [-Wunused-variable]
int f, ind=0;
^~~
# | 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... |