fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. inline int my_getchar_unlocked(){
  5.   static char buf[1048576];
  6.   static int s = 1048576;
  7.   static int e = 1048576;
  8.   if(s == e && e == 1048576){
  9.     e = fread_unlocked(buf, 1, 1048576, stdin);
  10.     s = 0;
  11.   }
  12.   if(s == e){
  13.     return EOF;
  14.   }
  15.   return buf[s++];
  16. }
  17. inline void rd(int &x){
  18.   int k;
  19.   int m=0;
  20.   x=0;
  21.   for(;;){
  22.     k = my_getchar_unlocked();
  23.     if(k=='-'){
  24.       m=1;
  25.       break;
  26.     }
  27.     if('0'<=k&&k<='9'){
  28.       x=k-'0';
  29.       break;
  30.     }
  31.   }
  32.   for(;;){
  33.     k = my_getchar_unlocked();
  34.     if(k<'0'||k>'9'){
  35.       break;
  36.     }
  37.     x=x*10+k-'0';
  38.   }
  39.   if(m){
  40.     x=-x;
  41.   }
  42. }
  43. inline void rd(char &c){
  44.   int i;
  45.   for(;;){
  46.     i = my_getchar_unlocked();
  47.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  48.       break;
  49.     }
  50.   }
  51.   c = i;
  52. }
  53. inline int rd(char c[]){
  54.   int i;
  55.   int sz = 0;
  56.   for(;;){
  57.     i = my_getchar_unlocked();
  58.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  59.       break;
  60.     }
  61.   }
  62.   c[sz++] = i;
  63.   for(;;){
  64.     i = my_getchar_unlocked();
  65.     if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
  66.       break;
  67.     }
  68.     c[sz++] = i;
  69.   }
  70.   c[sz]='\0';
  71.   return sz;
  72. }
  73. inline int rd_int(void){
  74.   int x;
  75.   rd(x);
  76.   return x;
  77. }
  78. struct MY_WRITER{
  79.   char buf[1048576];
  80.   int s;
  81.   int e;
  82.   MY_WRITER(){
  83.     s = 0;
  84.     e = 1048576;
  85.   }
  86.   ~MY_WRITER(){
  87.     if(s){
  88.       fwrite_unlocked(buf, 1, s, stdout);
  89.     }
  90.   }
  91. }
  92. ;
  93. MY_WRITER MY_WRITER_VAR;
  94. void my_putchar_unlocked(int a){
  95.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  96.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  97.     MY_WRITER_VAR.s = 0;
  98.   }
  99.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  100. }
  101. inline void wt_L(char a){
  102.   my_putchar_unlocked(a);
  103. }
  104. inline void wt_L(int x){
  105.   int s=0;
  106.   int m=0;
  107.   char f[10];
  108.   if(x<0){
  109.     m=1;
  110.     x=-x;
  111.   }
  112.   while(x){
  113.     f[s++]=x%10;
  114.     x/=10;
  115.   }
  116.   if(!s){
  117.     f[s++]=0;
  118.   }
  119.   if(m){
  120.     my_putchar_unlocked('-');
  121.   }
  122.   while(s--){
  123.     my_putchar_unlocked(f[s]+'0');
  124.   }
  125. }
  126. inline void wt_L(const char c[]){
  127.   int i=0;
  128.   for(i=0;c[i]!='\0';i++){
  129.     my_putchar_unlocked(c[i]);
  130.   }
  131. }
  132. template<class S, class T> inline S chmin(S &a, T b){
  133.   if(a>b){
  134.     a=b;
  135.   }
  136.   return a;
  137. }
  138. int TEST;
  139. int N;
  140. int Q;
  141. int S[100000];
  142. int X;
  143. int Y;
  144. char buf[22];
  145. int len;
  146. int dist[26][26];
  147. int res[100000];
  148. int main(){
  149.   int Lj4PdHRW = rd_int();
  150.   for(TEST=(0);TEST<(Lj4PdHRW);TEST++){
  151.     int i, j, k, q;
  152.     wt_L("Case #");
  153.     wt_L(TEST+1);
  154.     wt_L(": ");
  155.     rd(N);
  156.     rd(Q);
  157.     for(i=(0);i<(N);i++){
  158.       int j;
  159.       len = rd(buf);
  160.       S[i] = 0;
  161.       for(j=(0);j<(len);j++){
  162.         S[i] |= (1<<(buf[j]-'A'));
  163.       }
  164.     }
  165.     for(j=(0);j<(26);j++){
  166.       int k;
  167.       for(k=(0);k<(26);k++){
  168.         dist[j][k] = 1073709056;
  169.       }
  170.     }
  171.     for(i=(0);i<(26);i++){
  172.       dist[i][i] = 0;
  173.     }
  174.     for(i=(0);i<(N);i++){
  175.       for(j=(0);j<(26);j++){
  176.         if(((S[i]) &(1<<(j)))){
  177.           int k;
  178.           for(k=(j+1);k<(26);k++){
  179.             if(((S[i]) &(1<<(k)))){
  180.               dist[j][k] = dist[k][j] = 1;
  181.             }
  182.           }
  183.         }
  184.       }
  185.     }
  186.     for(k=(0);k<(26);k++){
  187.       for(i=(0);i<(26);i++){
  188.         for(j=(0);j<(26);j++){
  189.           chmin(dist[i][j], dist[i][k] + dist[k][j]);
  190.         }
  191.       }
  192.     }
  193.     for(q=(0);q<(Q);q++){
  194.       rd(X);X += (-1);
  195.       rd(Y);Y += (-1);
  196.       res[q] = 1073709056;
  197.       if(S[X] & S[Y]){
  198.         res[q] = 2;
  199.         continue;
  200.       }
  201.       for(j=(0);j<(26);j++){
  202.         if(((S[X]) &(1<<(j)))){
  203.           for(k=(0);k<(26);k++){
  204.             if(((S[Y]) &(1<<(k)))){
  205.               chmin(res[q], dist[j][k]+2);
  206.             }
  207.           }
  208.         }
  209.       }
  210.       if(res[q]==1073709056){
  211.         res[q] = -1;
  212.       }
  213.     }
  214.     {
  215.       int zT28qSmp;
  216.       if(Q==0){
  217.         wt_L('\n');
  218.       }
  219.       else{
  220.         for(zT28qSmp=(0);zT28qSmp<(Q-1);zT28qSmp++){
  221.           wt_L(res[zT28qSmp]);
  222.           wt_L(' ');
  223.         }
  224.         wt_L(res[zT28qSmp]);
  225.         wt_L('\n');
  226.       }
  227.     }
  228.   }
  229.   return 0;
  230. }
  231. // cLay varsion 20201115-2
  232.  
  233. // --- original code ---
  234. // int TEST;
  235. // int N, Q, S[1d5], X, Y;
  236. // char buf[22]; int len;
  237. // int dist[26][26];
  238. // int res[1d5];
  239. // {
  240. //   REP(TEST,rd_int()){
  241. //     wtF("Case #{TEST+1}: ");
  242. //     rd(N,Q);
  243. //     rep(i,N){
  244. //       rd(buf@len);
  245. //       S[i] = 0;
  246. //       rep(j,len) S[i] |= (1<<(buf[j]-'A'));
  247. //     }
  248. //     rep(j,26) rep(k,26) dist[j][k] = int_inf;
  249. //     rep(i,26) dist[i][i] = 0;
  250. //     rep(i,N) rep(j,26) if(BIT_ith(S[i],j)) rep(k,j+1,26) if(BIT_ith(S[i],k)) dist[j][k] = dist[k][j] = 1;
  251. //     rep(k,26) rep(i,26) rep(j,26) dist[i][j] <?= dist[i][k] + dist[k][j];
  252. //     rep(q,Q){
  253. //       rd(X--, Y--);
  254. //       res[q] = int_inf;
  255. //       if(S[X] & S[Y]) res[q] = 2, continue;
  256. //       rep(j,26) if(BIT_ith(S[X],j)) rep(k,26) if(BIT_ith(S[Y],k)) res[q] <?= dist[j][k]+2;
  257. //       if(res[q]==int_inf) res[q] = -1;
  258. //     }
  259. //     wt(res(Q));
  260. //   }
  261. // }
  262.  
Time limit exceeded #stdin #stdout 5s 4412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DTDqFf
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

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!