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;
const int maxn = 505;
vector<pair<int,int>> adj[maxn];
int vis[maxn], cnt;
vector<int> used;
void dfs(int u) {
vis[u] = cnt;
for (auto [v, id]:adj[u]) if (!vis[v]) {
used.push_back(id);
dfs(v);
}
}
vector<int> find_roads(int n, vector<int> U, vector<int> V) {
for (int i=0;i<U.size();i++) {
adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});
}
vector<int> golden;
int ans[U.size()];
for (int i=0;i<U.size();i++) ans[i] = -1;
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) vis[j] = 0;
vis[i] = -1;
cnt = 0;
used.clear();
vector<vector<int>> vec = {{}};
bool have = false;
for (auto [v, id]:adj[i]) {
if (ans[id]==-1) have = true;
if (vis[v]) vec[vis[v]].push_back(id);
else {
cnt++, vec.push_back({id});
dfs(v);
}
}
if (!have) continue;
for (int j=1;j<=cnt;j++) {
vector<int> thing = used;
for (int k=1;k<=cnt;k++) if (j!=k) thing.push_back(vec[k][0]);
vector<pair<int,int>> ret;
int mx = -1;
for (int v:vec[j]) {
thing.push_back(v);
if (ans[v]==-1) {
// cout << v << " " << ans[v] << endl;
// for (int X:thing) cout << X << " "; cout << endl;
ret.push_back({count_common_roads(thing), v});
} else {
if (ans[v]==1 && mx == -1) {
// for (int X:thing) cout << X << " "; cout << endl;
mx = count_common_roads(thing);
}
}
thing.pop_back();
}
mx = max(mx, (*max_element(ret.begin(), ret.end())).first);
for (auto [val, v]:ret) {
if (val==mx) golden.push_back(v);
ans[v] = (val==mx);
}
}
}
sort(golden.begin(), golden.end());
golden.erase(unique(golden.begin(), golden.end()), golden.end());
// for (int X:golden) cout << X << " "; cout << endl;
return golden;
}
Compilation message (stderr)
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int i=0;i<U.size();i++) {
| ~^~~~~~~~~
simurgh.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i=0;i<U.size();i++) ans[i] = -1;
| ~^~~~~~~~~
# | 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... |