Guest User

Untitled

a guest
Nov 24th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | None | 0 0
  1. #include <vector>
  2. #include <algorithm>
  3. #include <string.h>
  4. #include <stack>
  5. #include <string>
  6. #include <set>
  7. #include <queue>
  8. #include <map>
  9. #include <math.h>
  10. using namespace std;
  11.  
  12. #define f first
  13. #define s second
  14. #define mk make_pair
  15. #define pii pair<int,int>
  16.  
  17. typedef long long ll;
  18.  
  19. const int maxn = 200000 + 55;
  20. const int maxk = 20;
  21. const int prime = 1000000007;
  22.  
  23. int n,m;
  24. char txt[maxn][maxk];
  25.  
  26. ll start[maxn],end[maxn];
  27.  
  28. inline ll gethash( char *pok, int sz ){
  29.     ll ret = 0;
  30.     for( ; sz ; sz -- , pok ++ )
  31.         ret = ( ret * prime + *pok );
  32.     return ret;
  33. }
  34.  
  35. vector< pair<ll,char*> > lowtmp;
  36. void lower( ll *arr,  int n ){
  37.     for( int i = 0; i < n; ++i ){
  38.         int lo = 0, hi = lowtmp.size()-1;
  39.         int pos = -1;
  40.         while( lo <= hi ){
  41.             int mid = (lo+hi)>>1;
  42.             if( lowtmp[mid].f >= arr[i] ) hi = mid - 1 , pos = mid;
  43.             else lo = mid + 1;
  44.         }
  45.         arr[i] = pos;
  46.     }
  47. }
  48.  
  49. int cnte = 1;
  50. int head[maxn],point[maxn*2],nxt[maxn*2];
  51. int out[maxn];
  52. int in[maxn];
  53.  
  54. void add_edge( int a, int b ){
  55.     nxt[cnte] = head[a], point[cnte] = b, head[a] = cnte ++;
  56.     out[a] ++;
  57.     in[b] ++;
  58. }
  59.  
  60. stack<int>euler;
  61. int curr[maxn];
  62.  
  63. void dfs( int node ){
  64.  
  65.     while( curr[node] >= 1 ){
  66.         int w = point[ curr[node] ];
  67.         curr[node] = nxt[ curr[node] ];
  68.         dfs( w );
  69.     }
  70.     euler.push( node );
  71. }
  72.  
  73. char sol[maxn];
  74. bool done[maxn];
  75.  
  76. int main(){
  77.     scanf("%d%d",&n,&m);
  78.     int len = n;
  79.     n = n - m + 1;
  80.  
  81.     for( int i = 0; i < n; ++i ){
  82.         scanf("%s",txt[i]);
  83.         start[i] = gethash( txt[i], m - 1 );
  84.         end[i] = gethash( txt[i] + 1 , m - 1 );
  85.  
  86.         lowtmp.push_back( mk( start[i] , &txt[i][0] ) );
  87.         lowtmp.push_back( mk( end[i] , &txt[i][1] ) );
  88.     }
  89.  
  90.     sort( lowtmp.begin(), lowtmp.end() );
  91.     lower( start , n );
  92.     lower( end , n );
  93.  
  94.     for( int i = 0; i < n; ++i )
  95.         add_edge( start[i], end[i] );
  96.  
  97.     int s = 0;
  98.     for( int i = 0; i < 2*n; ++i ){
  99.         if( out[i] == in[i] + 1 ) s = i;
  100.         curr[i] = head[i];
  101.     }
  102.  
  103.     int sz = len - 1;
  104.     dfs( s );
  105.  
  106.     int u;
  107.     vector< int > us;
  108.     while( euler.empty() == false ){
  109.         u = euler.top();
  110.         euler.pop();
  111.         us.push_back(u);
  112.     }
  113.  
  114.     for( int i = us.size()-1; i >= 0; --i ){
  115.         u = us[i];
  116.         sol[sz--] = *(lowtmp[u].s+m-2);
  117.     }
  118.  
  119.     sol[len] = '\0';
  120.  
  121.     for( int i = 0; i < m-1; ++i )
  122.         sol[i] = *(lowtmp[u].s+i);
  123.  
  124.     printf("%s\n",sol);
  125.  
  126.     return 0;
  127. }
Add Comment
Please, Sign In to add comment