oj.uz

Submission #240899

# Submission time Handle Problem Language Result Execution time Memory
240899 2020-06-21T12:23:35 Z SamAnd Rima (COCI17_rima) C++17
140 / 140
 256 ms 68472 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 3000006;

int z;
int t[N][26];
bool c[N];

int n;
char a[N];

int ans;
int dp[N];

void dfs(int x)
{
    int max1 = 0, max2 = 0;
    int q = 0;
    for (int i = 0; i < 26; ++i)
    {
        int h = t[x][i];
        if (!h)
            continue;
        dfs(h);
        if (c[h])
        {
            if (dp[h] >= max1)
            {
                max2 = max1;
                max1 = dp[h];
            }
            else if (dp[h] >= max2)
                max2 = dp[h];
            ++q;
        }
    }
    ans = max(ans, max1 + max2 + q + c[x]);
    dp[x] = max1 + q;
}

void solv()
{
    int qq;
    scanf("%d", &qq);
    while (qq--)
    {
        scanf(" %s", a);
        n = strlen(a);
        reverse(a, a + n);
        int pos = 0;
        for (int i = 0; i < n; ++i)
        {
            if (!t[pos][a[i] - 'a'])
                t[pos][a[i] - 'a'] = ++z;
            pos = t[pos][a[i] - 'a'];
        }
        c[pos] = true;
    }
    dfs(0);
    printf("%d\n", ans);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message

rima.cpp: In function 'void solv()':
rima.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &qq);
     ~~~~~^~~~~~~~~~~
rima.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", a);
         ~~~~~^~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 256 ms 68472 KB Output is correct
5 Correct 34 ms 3576 KB Output is correct
6 Correct 59 ms 56696 KB Output is correct
7 Correct 58 ms 56560 KB Output is correct
8 Correct 57 ms 56440 KB Output is correct
9 Correct 87 ms 60280 KB Output is correct
10 Correct 60 ms 56440 KB Output is correct