fork download
copy 
  1. /*
  2.     --------------------------------DO NOT COPY I REQUEST YOU PLEASE--------------------------
  3.      
  4.     AUTHOR : Chandan Agrawal
  5.     College : Poornima College of Engg. jaipur, Raj
  6.     Mail : chandanagrawal23@gmail.com
  7.      
  8.     */
  9.  
  10.     #include<bits/stdc++.h>
  11.     #include<stdio.h>
  12.     using namespace std;
  13.  
  14.     #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  15.     #define MAX 100050
  16.  
  17.     #define ll long long
  18.     #define ld long double
  19.     #define lli long long int
  20.  
  21.     #define pb emplace_back
  22.     #define INF 1000000000
  23.     #define mod 1000000007
  24.     #define MOD 1000000007
  25.  
  26.     // trignometric function always give value in Radians only
  27.     #define PI acos(-1) //3.1415926535897932384626433832795028
  28.     #define dsin(degree) sin(degree*(PI/180.0))
  29.     #define dcos(degree) cos(degree*(PI/180.0))
  30.     #define dtan(degree) tan(degree*(PI/180.0))
  31.  
  32.     #define rsin(radian) sin(radian)
  33.     #define rcos(radian) cos(radian)
  34.     #define rtan(radian) tan(radian)
  35.  
  36.     #define loop(i,n) for (lli i = 0; i < n; i++)
  37.     #define loopitr(xt,vec) for (auto xt : vec)
  38.     #define FOR(i,a,b) for (lli i = a; i < b; i+=1)
  39.     #define loop_rev(i,n) for (lli i = n-1; i >= 0; i--)
  40.     #define FOR_REV(i,a,b) for (lli i = a; i >= b; i--)
  41.     #define itr :: iterator it
  42.     #define WL(t) while(t --)
  43.  
  44.     #define all(v) v.begin(),v.end()
  45.     #define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
  46.     #define sz(x) int(x.size())
  47.     #define F first
  48.     #define S second
  49.  
  50.     #define mii map<lli,lli>
  51.     #define vi vector<lli>
  52.     #define seti set<lli>
  53.     #define pii pair<lli,lli>
  54.  
  55.     #define gcd(a,b) __gcd((a),(b))
  56.     #define lcm(a,b) (a/gcd(a,b))*b
  57.     #define abs(x) ((x < 0)?-(x):x)
  58.  
  59.     template <typename T>
  60.     void print(T x){cout<<x<<endl;}
  61.     template <typename T1, typename T2>
  62.     void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
  63.     template <typename T1, typename T2,typename T3>
  64.     void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}
  65.  
  66.     #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  67.     #define scanvector(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.push_back(x);}
  68.  
  69.     #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  70.     #define printvector(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  71.     #define printset(st) for(auto xt : st) cout<<xt<<" ";    cout<<"\n";
  72.  
  73.     #define FD(N) fixed<<setprecision(N)
  74.  
  75.     #define endl '\n'
  76.  
  77.     #define deb(x) cout<<#x<<" "<<x<<endl;
  78.  
  79.     /*
  80.     ifstream cinn("i3.txt");
  81.     ofstream coutt("o3.txt");
  82.     */
  83.  
  84.  
  85.     bool isvowel(char v) { return (0x208222>>(v&0x1f))&1; }
  86.  
  87.     lli mceil(lli a,lli b){
  88.         if(a%b==0) return(a/b);
  89.         else return(a/b  +1);
  90.     }
  91.     lli mfloor(lli a,lli b){
  92.         return(a/b);
  93.     }
  94.  
  95.     ll modmul(ll a, ll b) {
  96.         return ((a%mod) * (b%mod)) % mod;
  97.     }
  98.  
  99.     ll modadd(ll a , ll b){
  100.         return((a%mod)+(b%mod)+mod)%mod;
  101.     }
  102.  
  103.     ll modsub(ll a , ll b){
  104.         return((a%mod) - (b%mod) + mod)%mod;
  105.     }
  106.  
  107.     lli fastexpo(lli a,lli b){
  108.         a = a%mod;
  109.         lli ans=1;
  110.         while(b){
  111.             if(b&1)
  112.                 ans=(ans*1ll*a)%mod;
  113.             a=(a*1ll*a)%mod;
  114.             b=b/2;
  115.             }
  116.         return ans;
  117.      }
  118.  
  119.  
  120.  
  121.      /* -----------------------------------------------------HASHING-------------------------------------------------------------------*/
  122.     /*
  123.     some key points -
  124.     1. Use (long int) to remove TLE or Memory Limit issue
  125.     2. If still Wrong answer then may be collision occur , use p as bigger prime no. p : [31,53,107,209,4793]
  126.     3. use mod either 1e9+7
  127.     4 .If it still shows WA then surely collision occurs use Double Hashing
  128.        Double Hashing -
  129.             Make Prehash Array using two different p and mod so chances of collision is less
  130.     5. use pass by reference always
  131.      
  132.      
  133.     */
  134.  
  135.  
  136.     #define maxlen 100005 //maximum length of string
  137.  
  138.     lli pow_p1[maxlen];
  139.     lli p_inv1[maxlen];
  140.     lli pow_p2[maxlen];
  141.     lli p_inv2[maxlen];
  142.  
  143.  
  144.     void init(lli p1, lli p2)
  145.     {
  146.         pow_p1[0] = p_inv1[0] = pow_p2[0] = p_inv2[0] = 1;
  147.         lli pinv1 = fastexpo(p1,mod-2);
  148.         lli pinv2 = fastexpo(p2,mod-2);
  149.         for(lli i=1;i<maxlen;i++)
  150.         {
  151.             pow_p1[i] = modmul(pow_p1[i-1],p1);
  152.             p_inv1[i] = modmul(p_inv1[i-1],pinv1);
  153.             pow_p2[i] = modmul(pow_p2[i-1],p2);
  154.             p_inv2[i] = modmul(p_inv2[i-1],pinv2);
  155.         }
  156.  
  157.     }
  158.  
  159.     struct Hash{
  160.             // 0 based indexing
  161.             lli prehash1[maxlen];
  162.             lli prehash2[maxlen];
  163.             // hash(s) = sigma(i=0 to n-1) s[i]*p^(i)
  164.             // a->1 , b->2 , c->3 and so on
  165.  
  166.  
  167.              void precomputehash(vi &s){ //p can be any prime 19 , 31, 53,107 ...
  168.  
  169.  
  170.               prehash2[0] = prehash1[0] = (s[0]+1);
  171.  
  172.                 for (lli i=1;i<s.size();i++) {
  173.                     prehash1[i]= modadd(prehash1[i-1] , modmul((s[i]+1),pow_p1[i]));
  174.                     prehash2[i]= modadd(prehash2[i-1] , modmul((s[i]+1),pow_p2[i]));
  175.                 }
  176.             }
  177.  
  178.             // hash[l..r] = ((hash[upto r] - hash[upto (l-1)] ) / P^l) % mod = ((hash[upto r] - hash[upto (l-1)] ) * modinv(P^l) )%mod
  179.             pii gethash(lli l, lli r){
  180.                 if(l==0)
  181.                     return(make_pair( (prehash1[r]%mod) , (prehash2[r]%mod) ) );
  182.                 else{
  183.                     lli ans1 = modsub(prehash1[r],prehash1[l-1]);
  184.                     ans1 = modmul(ans1, p_inv1[l]);
  185.  
  186.                     lli ans2 = modsub(prehash2[r],prehash2[l-1]);
  187.                     ans2 = modmul(ans2, p_inv2[l]);
  188.  
  189.                     return (make_pair(ans1,ans2));
  190.                 }
  191.             }
  192.  
  193.             // hash value of all string means hash[0..(n-1)] // 0 based indexing
  194.             pii totalhash(vi &s){
  195.                 return(make_pair(prehash1[sz(s)-1]%mod , prehash2[sz(s)-1]%mod));
  196.             }
  197.     };
  198.  
  199.  
  200. bool check(Hash *obj , vector<vi> paths , lli n , lli mid)
  201. {
  202.     map<pair<lli ,lli>,lli>mp;
  203.     set<pair<lli,lli>>st1;
  204.     for(int j=0;j<=sz(paths[0])-mid;j+=1)
  205.     {
  206.         st1.insert(obj[0].gethash(j,j+mid-1));
  207.     }
  208.     for(auto xt : st1)
  209.         mp[xt]++;
  210.     for(int i=1;i<n;i++)
  211.     {
  212.         set<pair<lli,lli>>st;
  213.         for(int j=0;j<=sz(paths[i])-mid;j+=1)
  214.         {
  215.             st.insert(obj[i].gethash(j,j+mid-1));
  216.         }
  217.  
  218.         for(auto xt : st)
  219.         {
  220.             if(st1.find(xt)!=st1.end())
  221.             {
  222.                 mp[xt]++;
  223.             }
  224.         }
  225.     }
  226.     for(auto xt : mp)
  227.     {
  228.         if(xt.S==n)
  229.             return true;
  230.     }
  231.     return false;
  232. }
  233.  
  234. class Solution {
  235. public:
  236.     int longestCommonSubpath(int nn, vector<vector<int>>& path) {
  237.         init(53,4793);
  238.         lli n = path.size();
  239.         vector<vi>paths;
  240.         for(auto xt : path)
  241.         {
  242.             vi tmp;
  243.             for(auto xr : xt)
  244.             {
  245.                 tmp.pb(1LL*xr);
  246.             }
  247.             paths.pb(tmp);
  248.         }
  249.         Hash obj[n];
  250.         lli mini = INF;
  251.         for(int i=0;i<n;i++){
  252.             obj[i].precomputehash(paths[i]);
  253.             if(mini  >sz(paths[i]))
  254.                 mini = sz(paths[i]);
  255.         }
  256.  
  257.         lli l=1 , r = mini , ans = 0;
  258.         while(l<=r)
  259.         {
  260.             lli mid = (l+r)/2;
  261.             if(check(obj , paths , n , mid))
  262.             {
  263.                 ans = mid;
  264.                 l = mid+1;
  265.             }
  266.             else
  267.                 r=mid-1;
  268.         }
  269.  
  270.         return ans;
  271.  
  272.  
  273.     }
  274. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/KKPf2q
language:
C++14 (gcc 8.3)
created:
2 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!