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;
#define ll int
#define ff first
#define ss second
#define ln "\n"
#define ld long double
vector<pair<ll, ll>> e;
vector<vector<ll>> A;
vector<ll> checka;
void dfs(ll u, vector<bool> &vis, ll mask){
vis[u]=1;
for (auto i:A[u]){
if (mask&(1<<i)){
ll v = e[i].ff^e[i].ss^u;
if (vis[v]) continue;
dfs(v, vis, mask);
}
}
}
bool check(ll mask, ll n, ll m){
checka.clear();
vector<bool> vis(n);
dfs(0, vis, mask);
for (ll i=0; i<n; i++) if (!vis[i]) return 0;
for (ll i=0; i<m; i++){
if (mask&(1<<i)) checka.push_back(i);
}
return 1;
}
// Slow version
vector<int> find_roads(int _n, vector<int> u, vector<int> v) {
int n=_n, m=u.size();
e.resize(m); A.clear(); A.resize(n);
for (ll i=0; i<m; i++){
e[i]={u[i], v[i]};
A[u[i]].push_back(i); A[v[i]].push_back(i);
}
vector<ll> ans;
// cout << (1ll<<21) << ln;
for (ll i=0; i<(1ll<<m); i++){
// cout << i << "-";
// cout << i << "-" << (1ll<<m) << ln;
if (__builtin_popcount(i)==n-1){
// cout << i << ": ";
if (check(i, n, m)) {
// cout << "Check: ";
// for (auto ch:checka) cout << ch << " ";
// cout << ln;
ll ret = count_common_roads(checka);
// cout << "FOUND: " << ": ";
if (ret==n-1){
ans=checka; break;
}
}
// cout << ln;
}
}
// assert(ans.size());
return ans;
}
# | 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... |