Submission #803117

#	Time	Username	Problem	Language	Result	Execution time	Memory
803117		Augustyn	Palindromi (COCI22_palindromi)	C++17	110 / 110	189 ms	72856 KiB

Main

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
struct pal_tree_node
{
    int dlug;
    long long hasz;
    pal_tree_node *shrt[2], *syn[2];
    pal_tree_node(int xd,long long hz)
    {
        dlug=xd;
        hasz=hz;
        shrt[0]=shrt[1]=syn[0]=syn[1]=NULL;
    }
};
struct lista
{
    int wart;
    int l, r;
    lista(int a)
    {
        wart=a;
        l=-1;
        r=-1;
    }
    lista()
    {
        wart=0;
        l=-1;
        r=-1;
    }
};

vector<int>nal;
vector<bool>seq;
vector<pal_tree_node*>pref,suf;
pal_tree_node* pust;
pal_tree_node* jz[2];
void ini(int n)
{
    nal.resize(n);
    seq.resize(n);
    pref.resize(n);
    suf.resize(n);
    pust = new pal_tree_node(0,0);
    jz[0] = new pal_tree_node(1,50000000000001);
    jz[1] = new pal_tree_node(1,50000000000002);
    jz[0]->shrt[0]=jz[1]->shrt[1]=pust;
}
int znajdz(int ter)
{
    if(nal[ter]==ter)
        return ter;
    nal[ter]=znajdz(nal[ter]);
    return nal[ter];
}
int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    ini(n);
    vector<int>sz(n);
    vector<lista>akt_ciag(n);
    vector<pair<int,int>>po(n);
    vector<unordered_map<long long,bool>>mapy(n);
    vector<vector<long long>>tusa(n);
    vector<int>konc(n),gdzie_w_konc(n);
    for(int i=0;i<n;++i)
    {
        char wcz;
        cin>>wcz;
        wcz-='0';
        seq[i]=wcz;
        nal[i]=i;
        pref[i]=suf[i]=jz[wcz];
        akt_ciag[i].l=akt_ciag[i].r=-1;
        akt_ciag[i].wart=i;
        po[i].first=po[i].second=i;
        tusa[i].push_back(wcz+1);
        sz[i]=1;
        mapy[i][wcz+1]=1;
    }
    vector<pair<int,int>>zlacz(n-1);
    for(int ile_merge=0;ile_merge<n-1;++ile_merge)
    {
        cin>>zlacz[ile_merge].first>>zlacz[ile_merge].second;
        --zlacz[ile_merge].first; --zlacz[ile_merge].second;
        int a,b;
        a=zlacz[ile_merge].first; b=zlacz[ile_merge].second;
        a=znajdz(a);
        b=znajdz(b);
        akt_ciag[po[a].second].r=po[b].first;
        akt_ciag[po[b].first].l=po[a].second;
        po[a].second=po[b].second;
        nal[b]=a;
    }
    int tut=po[znajdz(0)].first;
    for(int i=0;i<n;++i)
    {
        gdzie_w_konc[tut]=i;
        konc[i]=tut;
        po[tut].first=po[tut].second=i;
        tut=akt_ciag[tut].r;
    }

    for(int i=0;i<n;++i)
    {
        akt_ciag[i].l=akt_ciag[i].r=-1;
        nal[i]=i;
        po[i].first=po[i].second=gdzie_w_konc[i];
    }
    int a,b;
    for(int ile_merge=0;ile_merge<n-1;++ile_merge)
    {
        a=znajdz(zlacz[ile_merge].first); b=znajdz(zlacz[ile_merge].second);
        if(po[a].second-po[a].first<=po[b].second-po[b].first)
        {
            pal_tree_node* najd=pref[b];
            for(int i=po[a].second;i>=po[a].first;--i)
            {
                if(najd->dlug==po[b].second-i)
                {
                    najd=najd->shrt[seq[konc[i]]];
                    if(najd==NULL)
                        najd=pust;
                }
                if(najd->dlug!=0)
                    if(seq[konc[i+1+(najd->dlug)]]!=seq[konc[i]])
                    {
                        najd=najd->shrt[seq[konc[i]]];
                        if(najd==NULL)
                            najd=pust;
                    }
                if(najd->dlug==0)
                {
                    if(seq[konc[i+1]]==seq[konc[i]])
                    {
                        //dwie takie same
                        if(pust->syn[seq[konc[i]]]==NULL)
                        {
                            pal_tree_node* pom= new pal_tree_node(2,(seq[konc[i]]+1)*4);
                            pust->syn[seq[konc[i]]]=pom;
                            pom->shrt[seq[konc[i]]]=jz[seq[konc[i]]];
                        }
                        najd=pust->syn[seq[konc[i]]];
                        if(mapy[b][(seq[konc[i]]+1)*4]!=1)
                        {
                            mapy[b][(seq[konc[i]]+1)*4]=1;
                            tusa[b].push_back((seq[konc[i]]+1)*4);
                            ++sz[b];
                        }
                    }
                    else
                    {
                        //jeden taki sam
                        najd=jz[seq[konc[i]]];
                        if(mapy[b][seq[konc[i]]+1]!=1)
                        {
                            mapy[b][seq[konc[i]]+1]=1;
                            tusa[b].push_back(seq[konc[i]]+1);
                            ++sz[b];
                        }
                    }
                }
                else
                {
                    //dodajemy normalnie
                    if(najd->syn[seq[konc[i]]]==NULL)
                    {
                        //dodaj wierz
                        pal_tree_node* pom= new pal_tree_node((najd->dlug)+2,(najd->hasz)*3+seq[konc[i]]+1);
                        najd->syn[seq[konc[i]]]=pom;
                        //znajdz pom->shrt
                        pal_tree_node* pom2=najd->shrt[seq[konc[i]]];
                        if(pom2==NULL)
                            pom2=jz[seq[konc[i]]];
                        else
                            pom2=pom2->syn[seq[konc[i]]];
                        //no i teraz musze wiedziec co jest po nim
                        int x=seq[konc[i+pom2->dlug]];
                        pom->shrt[x]=pom2;
                        pom2=pom2->shrt[1-x];
                        pom->shrt[1-x]=pom2;
                    }
                    najd=najd->syn[seq[konc[i]]];
                    if(mapy[b][najd->hasz]!=1)
                    {
                        mapy[b][najd->hasz]=1;
                        tusa[b].push_back(najd->hasz);
                        ++sz[b];
                    }
                }
                //sprawdz czy najd jest sufixem b
                if(najd->dlug==po[b].second-i+1)
                    suf[b]=najd;
            }
            pref[b]=najd;
            po[b].first=po[a].first;
            nal[a]=b;
            for(auto i:tusa[a])
            {
                if(mapy[b][i]!=1)
                {
                    mapy[b][i]=1;
                    tusa[b].push_back(i);
                    ++sz[b];
                }
            }
            a=b;
        }
        else
        {
            pal_tree_node* najd=suf[a];
            for(int i=po[b].first;i<=po[b].second;++i)
            {
                if(najd->dlug==i-po[a].first)
                {
                    najd=najd->shrt[seq[konc[i]]];
                    if(najd==NULL)
                        najd=pust;
                }
                if(najd->dlug!=0)
                    if(seq[konc[i-1-(najd->dlug)]]!=seq[konc[i]])
                    {
                        najd=najd->shrt[seq[konc[i]]];
                        if(najd==NULL)
                            najd=pust;
                    }
                if(najd->dlug==0)
                {
                    if(seq[konc[i-1]]==seq[konc[i]])
                    {
                        //dwie takie same
                        if(pust->syn[seq[konc[i]]]==NULL)
                        {
                            pal_tree_node* pom= new pal_tree_node(2,(seq[konc[i]]+1)*4);
                            pust->syn[seq[konc[i]]]=pom;
                            pom->shrt[seq[konc[i]]]=jz[seq[konc[i]]];
                        }
                        najd=pust->syn[seq[konc[i]]];
                        if(mapy[a][(seq[konc[i]]+1)*4]!=1)
                        {
                            mapy[a][(seq[konc[i]]+1)*4]=1;
                            tusa[a].push_back((seq[konc[i]]+1)*4);
                            ++sz[a];
                        }
                    }
                    else
                    {
                        //jeden taki sam
                        najd=jz[seq[konc[i]]];
                        if(mapy[a][seq[konc[i]]+1]!=1)
                        {
                            mapy[a][seq[konc[i]]+1]=1;
                            tusa[a].push_back(seq[konc[i]]+1);
                            ++sz[a];
                        }
                    }
                }
                else
                {
                    //dodajemy normalnie
                    if(najd->syn[seq[konc[i]]]==NULL)
                    {
                        //dodaj wierz
                        pal_tree_node* pom= new pal_tree_node((najd->dlug)+2,(najd->hasz)*3+seq[konc[i]]+1);
                        najd->syn[seq[konc[i]]]=pom;
                        //znajdz pom->shrt
                        pal_tree_node* pom2=najd->shrt[seq[konc[i]]];
                        if(pom2==NULL)
                            pom2=jz[seq[konc[i]]];
                        else
                            pom2=pom2->syn[seq[konc[i]]];
                        //no i teraz musze wiedziec co jest po nim
                        int x=seq[konc[i-pom2->dlug]];
                        pom->shrt[x]=pom2;
                        pom2=pom2->shrt[1-x];
                        pom->shrt[1-x]=pom2;
                    }
                    najd=najd->syn[seq[konc[i]]];
                    if(mapy[a][najd->hasz]!=1)
                    {
                        mapy[a][najd->hasz]=1;
                        tusa[a].push_back(najd->hasz);
                        ++sz[a];
                    }
                }
                //sprawdz czy najd jest sufixem b
                if(najd->dlug==i-po[a].first+1)
                    pref[a]=najd;
            }
            suf[a]=najd;
            po[a].second=po[b].second;
            nal[b]=a;
            for(auto i:tusa[b])
            {
                if(mapy[a][i]!=1)
                {
                    mapy[a][i]=1;
                    tusa[a].push_back(i);
                    ++sz[a];
                }
            }
            b=a;
        }
        printf("%d\n",sz[a]);
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:77:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   77 |         pref[i]=suf[i]=jz[wcz];
      |                           ^~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50