fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MP make_pair
  3. #define PB push_back
  4. #define int long long
  5. #define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
  6. #define RE(i, n) FOR(i, 1, n)
  7. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  8. #define REP(i, n) for(int i = 0;i <(n); ++i)
  9. #define VAR(v, i) __typeof(i) v=(i)
  10. #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  11. #define ALL(x) (x).begin(), (x).end()
  12. #define SZ(x) ((int)(x).size())
  13. #ifdef LOCAL
  14. #define debug(x) {cerr <<#x <<" = " <<x <<"\n"; }
  15. #define debug2(x, y) {cerr <<#x <<" = " <<x <<", "<<#y <<" = " <<y <<"\n";}
  16. #define debug3(x, y, z) {cerr <<#x <<" = " <<x <<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<"\n";}
  17. #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
  18. using std::cerr;
  19. #else
  20. #define debug(x)
  21. #define debug2(x, y)
  22. #define debug3(x, y, z)
  23. #define debugv(x)
  24. #define cerr if(0)cout
  25. #endif
  26. #define make(type, x) type x; cin>>x;
  27. #define make2(type, x, y) type x, y; cin>>x>>y;
  28. #define make3(type, x, y, z) type x, y, z; cin>>x>>y>>z;
  29. #define make4(type, x, y, z, t) type x, y, z, t; cin>>x>>y>>z>>t;
  30. using std::endl;
  31. using std::cout;
  32. using std::cin;
  33. using std::vector;
  34. using std::set;
  35. using std::map;
  36. using std::pair;
  37. using std::max;
  38. using std::min;
  39. using std::ostream;
  40. using std::fixed;
  41. using std::ios_base;
  42. using std::setprecision;
  43. using std::make_pair;
  44. using std::string;
  45. using std::multiset;
  46. using std::next_permutation;
  47. using std::prev_permutation;
  48. using std::random_shuffle;
  49. using std::greater;
  50. using std::lower_bound;
  51. using std::upper_bound;
  52. using std::reverse;
  53. using std::swap;
  54. using std::complex;
  55. using std::sort;
  56. using std::bitset;
  57. using std::unordered_set;
  58. typedef long long ll;
  59. typedef long double LD;
  60. typedef pair<int, int> PII;
  61. typedef pair<ll, ll> PLL;
  62. typedef vector<int> VI;
  63. typedef vector<ll> VLL;
  64. typedef vector<pair<int, int> > VPII;
  65. typedef vector<pair<ll, ll> > VPLL;
  66.  
  67. template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
  68. template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
  69. template<class T1, class T2>
  70. ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
  71.  
  72. const int N = 15;
  73. unordered_set<int> dp[1 << N][N];
  74. int dis[N][N];
  75. int n, l;
  76. int full_mask;
  77. void Dfs(int mask, int v, int used, int len) {
  78.   if (2 * used + 1 >= n) {
  79.     dp[mask][v].insert(len);
  80.     if (v != 1) {
  81.       int cor_mask = full_mask - mask + (1 << (v - 2));
  82.       if (dp[cor_mask][v].count(l - len)) {
  83.         cout<<"possible"<<endl;
  84.         exit(0);
  85.       }
  86.     }
  87.   }
  88.   if (2 * used >= n) {
  89.     return;
  90.   }
  91.   FOR (nei, 2, n) {
  92.     int nei_bit = nei - 2;
  93.  
  94.     if (((1 << nei_bit) & mask) == 0) {
  95.       int new_mask = mask + (1 << nei_bit);
  96.       if (len + dis[v][nei] <= l) {
  97.         Dfs(new_mask, nei, used + 1, len + dis[v][nei]);
  98.       }
  99.     }
  100.   }
  101. }
  102.  
  103. #undef int
  104. int main() {
  105. #define int long long
  106.  
  107.   ios_base::sync_with_stdio(0);
  108.   cout << fixed << setprecision(10);
  109.   beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  110.   TimeStamp();
  111.   cin>>n>>l;
  112.   RE (i, n) {
  113.     RE (j, n) {
  114.       cin>>dis[i][j];
  115.     }
  116.   }
  117.   full_mask = (1 << (n - 1)) - 1;
  118.   Dfs(0, 1, 0, 0);
  119.   cout<<"impossible\n";
  120.  
  121.   return 0;
  122. }
  123.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:109:3: error: ‘beg_clock’ was not declared in this scope
   beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
   ^
prog.cpp:110:13: error: ‘TimeStamp’ was not declared in this scope
   TimeStamp();
             ^
stdout
copy 
Standard output is empty
https://ideone.com/cuWbcC
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!