Submission #91862

#	Time	Username	Problem	Language	Result	Execution time	Memory
91862		vex	Savez (COCI15_savez)	C++14	0 / 120	61 ms	66560 KiB

savez

#include <bits/stdc++.h>
#define maxn 2000005
#define MOD1 int(1e9 + 7)
#define MOD2 int(1e9 + 9)
#define p1 253
#define p2 257
using namespace std;

int n;
vector<pair<int,int>>hsh[maxn];
map<pair<int,int>,int>poz;
map<string,int>br;
string s[maxn];

long long ste(int x,int y,int mod)
{
    if(y==0)return 1;
    if(y%2==1)return (x*ste(x,y-1,mod))%mod;

    long long rrr=ste(x,y/2,mod);
    return (rrr*rrr)%mod;
}
long long ste_p1[maxn];
long long ste_p2[maxn];
long long inv_p1[maxn];
long long inv_p2[maxn];
void precalc()
{
    ste_p1[0]=1LL;
    ste_p2[0]=1LL;
    for(int i=1;i<maxn-3;i++)
    {
        ste_p1[i]=(ste_p1[i-1]*p1)%MOD1;
        ste_p2[i]=(ste_p2[i-1]*p2)%MOD2;
    }
    for(int i=0;i<maxn-3;i++)
    {
        inv_p1[i]=ste(ste_p1[i],MOD1-2,MOD1);
        inv_p2[i]=ste(ste_p2[i],MOD2-2,MOD2);
    }
}
pair<int,int> hesh(int i,int l,int r)
{
    if(l==0)return hsh[i][r];
    return {((hsh[i][r].first-hsh[i][l-1].first+MOD1)*inv_p1[l])%MOD1,((hsh[i][r].second-hsh[i][l-1].second+MOD2)*inv_p2[l])%MOD2};
}

vector<int>adj[maxn];
int in[maxn];

vector<int>tps;
stack<int>ms;

int dp[maxn];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    precalc();
    //for(int i=0;i<5;i++)cout<<ste_p1[i]<<","<<inv_p1[i]<<" ";cout<<endl;
    //for(int i=0;i<5;i++)cout<<ste_p2[i]<<","<<inv_p2[i]<<" ";cout<<endl;

    ///PRVI DEO --> UCITAVANJE I HESIRANJE
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        br[s[i]]++;
        if(br[s[i]]>1)continue;

        int len=s[i].size();

        hsh[i].push_back({s[i][0]-'A'+1,s[i][0]-'A'+1});

        for(int j=1;j<len;j++)
        {
            long long h1=hsh[i][j-1].first+(ste_p1[j]*(s[i][j]-'A'+1))%MOD1;h1%=MOD1;
            long long h2=hsh[i][j-1].second+(ste_p2[j]*(s[i][j]-'A'+1))%MOD2;h2%=MOD2;
            hsh[i].push_back({h1,h2});
        }

        //for(int j=0;j<len;j++)cout<<hsh[i][j].first<<","<<hsh[i][j].second<<" ";cout<<endl;cout<<endl;

        poz[hsh[i][len-1]]=i;
    }



    ///DRUGI DEO --> STVARANJE GRAFA
    for(int i=1;i<=n;i++)
    {
        int len=hsh[i].size();
        for(int j=0;j<len-1;j++)
        {
            int ppp=poz[hsh[i][j]];
            pair<int,int> hhh=hesh(i,len-j-1,len-1);
            //cout<<i<<","<<j<<" "<<ppp<<"   "<<hhh.first<<","<<hhh.second<<endl;
            if(ppp!=0 && hhh==hsh[i][j])
            {
                //cout<<ppp<<" "<<i<<endl;
                adj[ppp].push_back(i);
                in[i]++;
            }
        }
    }


    //cout<<"tps"<<endl;

    ///TRECI DEO --> TOP SORT
    for(int i=1;i<=n;i++)
    {
        if(in[i]==0)
        {
            ms.push(i);
        }
    }
    while(!ms.empty())
    {
        int x=ms.top();
        tps.push_back(x);
        ms.pop();

        for(auto v:adj[x])
        {
            in[v]--;
            if(in[v]==0)ms.push(v);
        }
    }

     //for(auto x:tps)cout<<x<<" ";cout<<endl;

    //cout<<"dp"<<endl;


    ///CETVRTI DEO --> DP
    dp[tps[n-1]]=br[s[n]];
    for(int i=n-2;i>=0;i--)
    {
        int v=tps[i];
        int poj=br[s[v]];
        dp[v]=poj;
        for(auto x:adj[v])
        {
            dp[v]=max(dp[v],dp[x]+poj);
        }
    }

    //cout<<"sss"<<endl;

    int maxx=0;
    for(int i=1;i<=n;i++)
    {
        maxx=max(maxx,dp[i]);
    }

    cout<<maxx<<endl;
    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12