This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//In the name of Allah the most beneficent, the most merciful.
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,avx512,fma")
#define int long long
#define ar array
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()
#define PI 3.1415926535897932384626433832795l
const int N = 12;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
// -------------------------<RNG>-------------------------
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers.
//--------------------------------------------------------
//int defined as long long
map<pair<int,int>,int> mp;
vector<int> adj[N];
int n,m;
int mask=0;
int vis=0;
int ed[N];
vector<int> path;
void dfs(int node){
vis|=(1<<node);
path.push_back(node);
for(auto i:adj[node])
if( ((vis&(1<<i))==0) && (mask&(1<<i)))
dfs(i);
}
bool check2(){
int sz=path.size();
if(sz<4)
return 0;
set<int> s;
for(auto i:path)
s.insert(i);
int szz=s.size();
if(szz!=sz)
return 0;
if(mp[{path[0],path[sz-1]}]==0)
return 0;
for(int i=0;i<sz-1;i++)
if(mp[{path[i],path[i+1]}]==0)
return 0;
for(int i=0;i<sz;i++)
for(int j=i+2;j<sz;j++)
if(mp[{path[i],path[j]}]&&(i!=0||j!=sz-1)){
cout<<i<<' '<<j<<endl;
return 0;
}
return 1;
}
bool check(){
for(int i=0;i<n;i++)
ed[i]=0;
for(int i=0;i<n;i++){
if((mask&(1<<i))==0)
continue;
for(int j=i+1;j<n;j++){
if((mask&(1<<j))==0)
continue;
ed[i]+=mp[{i,j}];
ed[j]+=mp[{i,j}];
}
}
for(int i=0;i<n;i++){
if((mask&(1<<i)) && ed[i]!=2)
return 0;
}
path.clear();
vis=0;
for(int i=0;i<n;i++)
if(mask&(1<<i)){
dfs(i);
break;
}
if(vis!=mask)
return 0;
if(check2()==0){
while(1);
}
cout<<path.size()<<endl;
for(auto i:path)
cout<<i+1<<' ';
cout<<endl;
return 1;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
if(n>10)
return 0;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;
b--;
mp[{a,b}]++;
mp[{b,a}]++;
adj[a].push_back(b);
adj[b].push_back(a);
}
while(mask<(1<<n)){
mask++;
if(__builtin_popcount(mask)<4)
continue;
if(check())
return 0;
}
cout<<"no"<<endl;
return 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... |
# | 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... |