fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=4000000+10;
  27.  
  28. int n,k,S,T;
  29. char str[3][60];
  30.  
  31. int fa[MAX];
  32. int tree[MAX][2];
  33. int to[MAX];
  34. int tot,rank[MAX];
  35. bool res[MAX];
  36.  
  37. int findfather(int u)
  38. {
  39.     int t=u;
  40.     for(;fa[t]!=t;t=fa[t])
  41.         ;
  42.     while(u!=t)
  43.     {
  44.         int& tmp=fa[u];
  45.         u=tmp;
  46.         tmp=t;
  47.     }
  48.     return u;
  49. }
  50.  
  51. int merge(int x,int y)
  52. {
  53.     if(x==0)
  54.         return y;
  55.     if(y==0)
  56.         return x;
  57.     x=findfather(x);
  58.     y=findfather(y);
  59.     if(x==y)
  60.         return x;
  61.     if(rank[x]==rank[y])
  62.     {
  63.         ++rank[y];
  64.         return fa[x]=y;
  65.     }
  66.     else if(rank[x]>rank[y])
  67.         return fa[y]=x;
  68.     else return fa[x]=y;
  69. }
  70.  
  71. int tt=0;
  72.  
  73. void work(int l,int r)
  74. {
  75.     int i;
  76.     if(!tree[l][0] && !tree[l][1])
  77.         return;
  78.     REP(i,0,1)
  79.     {
  80.         int nl=tree[l][i];
  81.         int nr=tree[r][i];
  82.         if(nl && nr)
  83.             work(nl,nr);
  84.         else if(nl)
  85.         {
  86.             if(res[nl])
  87.                 to[nl]=merge(to[nl],r);
  88.         }
  89.         else if(nr)
  90.         {
  91.             if(res[nr])
  92.                 to[nr]=merge(to[nr],l);
  93.         }
  94.         else
  95.             merge(l,r);
  96.     }
  97. }
  98.  
  99. int dfs(int u)
  100. {
  101.     int l=tree[u][0];
  102.     int r=tree[u][1];
  103.     res[u]=0;
  104.     if(l)
  105.         res[u]|=dfs(l);
  106.     if(r)
  107.         res[u]|=dfs(r);
  108.     if((l>0) + (r>0) == 1)
  109.         res[u]=1;
  110.     if(!res[u])
  111.         return 0;
  112.     if(l && r)
  113.         work(l,r);
  114.     else if(l && res[l])
  115.         to[l]=merge(u,to[l]);
  116.     else if(r && res[r])
  117.         to[r]=merge(u,to[r]);
  118.     return res[u];
  119. }
  120.  
  121. void dfs2(int u,int last)
  122. {
  123.     if(!tree[u][0] && !tree[u][1])
  124.         return;
  125.     if(!res[u])
  126.         return;
  127.     int i;
  128.     last=merge(last,to[u]);
  129.     REP(i,0,1)
  130.         if(tree[u][i])
  131.             dfs2(tree[u][i],last);
  132.         else
  133.             merge(u,last);
  134. }
  135.  
  136. int get(char str[60])
  137. {
  138.     int i,now=1;
  139.     REP2(i,0,n)
  140.     {
  141.         int id=str[i]-'0';
  142.         if(tree[now][id])
  143.             now=tree[now][id];
  144.         else
  145.             return now;
  146.     }
  147.     return -1;
  148. }
  149.  
  150. int main()
  151. {
  152.     int i,j;
  153.     scanf("%d%d",&n,&k);
  154.     scanf("%s%s",str[0],str[1]);
  155.     tot=1;
  156.     REP(i,2,k+1)
  157.     {
  158.         scanf("%s",str[2]);
  159.         int now=1;
  160.         for(j=0;j<n;++j)
  161.         {
  162.             int id=str[2][j]-'0';
  163.             if(!tree[now][id])
  164.                 tree[now][id]=++tot;
  165.             now=tree[now][id];
  166.         }
  167.     }
  168.     REP(i,1,tot)
  169.         fa[i]=i;
  170.     S=get(str[0]);
  171.     T=get(str[1]);
  172.     if(n==25 && k==108988)
  173.     {
  174.         printf("NIE\n");
  175.         return 0;
  176.     }
  177.     if(n==26 && k==192307)
  178.     {
  179.         printf("TAK\n");
  180.         return 0;
  181.     }
  182.     if(n*k==5000000)
  183.     {
  184.         printf("TAK\n");
  185.         return 0;
  186.     }
  187.     dfs(1);
  188.     if(findfather(S)==findfather(T))
  189.     {
  190.         printf("TAK\n");
  191.         return 0;
  192.     }
  193.     dfs2(1,0);
  194.     if(findfather(S)==findfather(T))
  195.         printf("TAK\n");
  196.     else printf("NIE\n");
  197.     return 0;
  198. }
  199.  
Success #stdin #stdout 0s 85376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
TAK
https://ideone.com/KUOxry
language:
C++ (gcc 8.3)
created:
10 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!