Submission #182416

#	Time	Username	Problem	Language	Result	Execution time	Memory
182416		XmtosX	Rima (COCI17_rima)	C++17	14 / 140	1068 ms	158252 KiB

rima

#include <bits/stdc++.h>
using namespace std;
int n,ans,memo[500004];
string s[500004];
vector <int> v[500004];
unordered_map<string, int> r;
bool vis[500004],fin[500004];
int dfs (int x)
{
    vis[x]=true;
    int &ret=memo[x];
    if (ret!=-1)
    {
        vis[x]=false;
        return ret;
    }
    int maxx=0;
    for (int i=0;i<v[x].size();i++)
    {
        if (!vis[v[x][i]])
            maxx=max(maxx,dfs(v[x][i])+1);
    }
    vis[x]=false;
    return ret=maxx;
}
int main()
{
    cin >>n;
    for (int i=1;i<=n;i++)
    {
        cin >>s[i];
        reverse(s[i].begin(),s[i].end());
        r[s[i]]=i;
    }
    for (int i=1;i<=n;i++)
    {
        for (int j='a';j<='z';j++)
        {
            s[i]+=j;
            if (r[s[i]])
            {
                    v[i].push_back(r[s[i]]);

                    v[r[s[i]]].push_back(i);
            }
            s[i].pop_back();
        }
        char c= s[i].back();
        s[i].pop_back();
        for (int j='a';j<='z';j++)
        {
            s[i]+=j;
            if (r[s[i]])
            {
                    v[i].push_back(r[s[i]]);
            }
            s[i].pop_back();
        }
        s[i]+=c;
    }
    memset(memo,-1,sizeof memo);
    for (int i=1;i<=n;i++)
    {
        if (!fin[i])
        ans=max(ans,dfs(i)+1);
    }
    cout <<ans;
    return 0;
}

Compilation message (stderr)

rima.cpp: In function 'int dfs(int)':
rima.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~

• Subtask 1: 14 / 140