Guest User

Untitled

a guest
Jul 23rd, 2014
341
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.94 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <ctime>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <string>
  9. #include <vector>
  10. #include <deque>
  11. #include <queue>
  12. #include <list>
  13. #include <set>
  14. #include <map>
  15.  
  16. #define pb push_back
  17. #define mp make_pair
  18. #define TASKNAME ""
  19.  
  20. #ifdef DEBUG
  21. #define eprintf(...) fprintf(stderr,__VA_ARGS__)
  22. #else
  23. #define eprintf(...)
  24. #endif
  25.  
  26. #define TIMESTAMP(x) eprintf("[" #x "] Time = %.3lfs\n",clock()*1.0/CLOCKS_PER_SEC)
  27.  
  28. #ifdef _WIN32
  29. #define LLD "%I64d"
  30. #else
  31. #define LLD "%lld"
  32. #endif
  33.  
  34. #define sz(x) ((int)(x).size())
  35. #define forn(i, n) for (int i = 0; i < (n); i++)
  36.  
  37. using namespace std;
  38.  
  39. typedef long double ld;
  40. typedef long long ll;
  41. typedef vector<ll> vll;
  42. typedef vector<int> vi;
  43. typedef vector<vi> vvi;
  44. typedef vector<bool> vb;
  45. typedef vector<vb> vvb;
  46. typedef pair<int, int> pii;
  47. typedef pair<ll, int> pli;
  48. typedef pair<int, ll> pil;
  49. typedef pair<ll, ll> pll;
  50. typedef vector<pii> vpii;
  51.  
  52. const int inf = 1e9;
  53. const double eps = 1e-9;
  54. const int INF = inf;
  55. const double EPS = eps;
  56.  
  57. #ifdef DEBUG
  58. struct __timestamper {
  59.   ~__timestamper(){
  60.     TIMESTAMP(end);
  61.   }
  62. } __Timestamper;
  63. #else
  64. struct __timestamper {};
  65. #endif
  66.  
  67. /*Template end*/
  68.  
  69. int get_fixed(int msk, const string &w) {
  70.   int res = 0;
  71.   for (int i = 0; i < sz(w); i++) {
  72.     if (msk & (1 << (w[i] - 'A'))) res |= 1 << i;
  73.   }
  74.   return res;
  75. }
  76.  
  77. int len;
  78. vector<string> ws;
  79. map<pii, bool> cache;
  80.  
  81. bool calc(int msk, int id) {
  82.   int fixed = get_fixed(msk, ws[id]);
  83.   if (fixed == (1 << len) - 1) return false;
  84.   {
  85.     int bad = msk;
  86.     forn (i, len)
  87.       bad &= ~(1 << (ws[id][i] - 'A'));
  88.     int bcnt = __builtin_popcount(bad);
  89.     if (bcnt > len) return true;
  90.   }
  91.  
  92.   if (cache.count(mp(msk, id))) return cache[mp(msk, id)];
  93.  
  94.   bool &res = cache[mp(msk, id)];
  95.   res = true;
  96.   for (int ne = 0; ne < 26; ne++) if (!(msk & (1 << ne))) {
  97.     bool cres = false;
  98.     for (int nid = 0; nid < sz(ws); nid++) {
  99.       if (get_fixed(msk, ws[nid]) != fixed) continue;
  100.  
  101.       bool cok = true;
  102.       forn (i, len) if (fixed & (1 << i)) {
  103.         cok = cok && ws[nid][i] == ws[id][i];
  104.       }
  105.       if (cok) {
  106.         cres = cres || calc(msk | (1 << ne), nid);
  107.       }
  108.     }
  109.     res = res && cres;
  110.   }
  111.   return res;
  112. }
  113.  
  114. bool solve() {
  115.   assert(!ws.empty());
  116.   len = sz(ws[0]);
  117.   cache.clear();
  118.   return calc(0, 0);
  119. }
  120.  
  121. int main() {
  122.   #ifdef DEBUG
  123.   freopen(TASKNAME".in","r",stdin);
  124.   #endif
  125.  
  126.   int TN;
  127.   assert(scanf("%d", &TN) == 1);
  128.   while (TN --> 0) {
  129.     int n;
  130.     scanf("%d", &n);
  131.     map<int, vector<string> > aws;
  132.     while (n --> 0) {
  133.       char str[10];
  134.       scanf("%s", str);
  135.       aws[strlen(str)].pb(str);
  136.     }
  137.     bool ok = false;
  138.     for (map<int, vector<string> >::const_iterator it = aws.begin(); it != aws.end(); it++) {
  139.       ws = it->second;
  140.       ok = ok || solve();
  141.     }
  142.     printf("%s\n", ok ? "Yes" : "No");
  143.   }
  144.   return 0;
  145. }
Advertisement
Add Comment
Please, Sign In to add comment