oj.uz

Submission #182413

# Submission time Handle Problem Language Result Execution time Memory
182413 2020-01-09T18:46:35 Z XmtosX Rima (COCI17_rima) C++17
42 / 140
 1000 ms 159476 KB 
#include <bits/stdc++.h>
using namespace std;
int n,ans;
string s[500004];
vector <int> v[500004];
unordered_map<string, int> r;
bool vis[500004],fin[500004];
int dfs (int x)
{
    vis[x]=true;
    fin[x]=true;
    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 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;
    }
    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:13:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28024 KB Output is correct
2 Correct 27 ms 27896 KB Output is correct
3 Correct 27 ms 27768 KB Output is correct
4 Execution timed out 1088 ms 112036 KB Time limit exceeded
5 Incorrect 390 ms 113960 KB Output isn't correct
6 Execution timed out 1039 ms 58772 KB Time limit exceeded
7 Execution timed out 1086 ms 53780 KB Time limit exceeded
8 Execution timed out 1040 ms 50324 KB Time limit exceeded
9 Execution timed out 1076 ms 159476 KB Time limit exceeded
10 Execution timed out 1075 ms 50708 KB Time limit exceeded