#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#define pii pair<int,int>
using namespace std;
const int nmax = 1001;
int mask[nmax];
int main(){
//ios_base::sync_with_stdio(false); cin.tie(0);
int n, m; cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v; cin >> u >> v;
u--;
v--;
mask[u] |= (1 << v);
mask[v] |= (1 << u);
}
for(int s = 0; s < n; s++){
int dp[(1 << n)][n];
for(int j = 0; j < (1 << n); j++){
for(int k = 0; k < n; k++)
dp[j][k] = -1;
}
dp[(1 << s)][s] = 0;
pii ans = {-1, -1};
for(int i = (1 << s) + 1; i < (1 << n); i++){
if(!(i & (1 << s))) continue;
for(int j = 0; j < n; j++){
if(j == s) continue;
if((1 << j) & i){
int m = mask[j] & (i ^ (1 << j));
int m1 = m & (i ^ (1 << s));
if(!m) continue;
if(m1 && __builtin_popcount(m1) > 1) continue;
if(!m1){
if(__builtin_popcount(i) == 2)
dp[i][j] = s;
}
if(m1){
int o = log2(m1);
if(dp[i ^ (1 << j)][o] != -1){
if(!(mask[j] & (1 << s)))dp[i][j] = o;
if(__builtin_popcount(i) < 4) continue;
if((mask[j] & (1 << s)) && ans.f == -1) ans = {i, j}, dp[i][j] = o;
}
}
}
}
}
if(ans.f == -1) continue;
while(ans.s != s){
cout << ans.s + 1<< ' ';
ans.f ^= (1 << ans.s);
ans.s = dp[ans.f ^ (1 << ans.s)][ans.s];
}
cout << s + 1;
return 0;
}
cout << "no\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
436 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
444 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
5052 KB |
Wrong answer on graph without induced cycle |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
5076 KB |
Wrong adjacency |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
26 ms |
1612 KB |
Wrong adjacency |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
1344 KB |
Wrong adjacency |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
526 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |