oj.uz

Submission #182416

# Submission time Handle Problem Language Result Execution time Memory
182416 2020-01-09T18:51:26 Z XmtosX Rima (COCI17_rima) C++17
14 / 140
 1000 ms 158252 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 29816 KB Output isn't correct
2 Correct 29 ms 29944 KB Output is correct
3 Incorrect 29 ms 29816 KB Output isn't correct
4 Execution timed out 1068 ms 109300 KB Time limit exceeded
5 Incorrect 391 ms 113284 KB Output isn't correct
6 Incorrect 150 ms 59780 KB Output isn't correct
7 Incorrect 117 ms 55188 KB Output isn't correct
8 Incorrect 96 ms 51932 KB Output isn't correct
9 Incorrect 976 ms 158252 KB Output isn't correct
10 Incorrect 99 ms 52244 KB Output isn't correct