oj.uz

Submission #367987

# Submission time Handle Problem Language Result Execution time Memory
367987 2021-02-19T07:20:10 Z TosakaUCW Rima (COCI17_rima) C++17
140 / 140
 308 ms 85356 KB 
#include <stdio.h>
#include <algorithm>
#include <memory.h>

int read(int x = 0, int f = 0, char ch = getchar())
{
    while ('0' > ch or ch > '9')
        f = ch == '-', ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

const int M = 3e6 + 5;

int n, nodecnt, ans;
int trie[M][30], sum[M], f[M];
bool tag[M];
char s[M];
std::pair<int, int> max[M];

void insert(char *s)
{
    int len = strlen(s + 1), p = 0;
    for (int i = len; i >= 1; i--)
    {
        if (!trie[p][s[i] - 'a'])
            trie[p][s[i] - 'a'] = ++nodecnt;
        p = trie[p][s[i] - 'a'];
    }
    tag[p] = true;
}

void dfs(int u)
{
    for (int i = 0, v; i < 26; i++)
        if (v = trie[u][i])
        {
            dfs(v);
            if (tag[v])
                sum[u]++;
            f[u] = std::max(f[u], f[v]);
            if (f[v] > max[u].first)
                max[u].second = max[u].first, max[u].first = f[v];
            else if (f[v] > max[u].second)
                max[u].second = f[v];
        }
    if (tag[u])
        f[u] += std::max(1, sum[u]);
    else
        f[u] = 0;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
        scanf("%s", s + 1), insert(s);
    dfs(0);
    for (int i = 0; i < nodecnt; i++)
        ans = std::max(ans, max[i].first + max[i].second + tag[i] + std::max(0, sum[i] - 2));
    return printf("%d", ans), 0;
}

Compilation message

rima.cpp: In function 'void dfs(int)':
rima.cpp:37:15: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   37 |         if (v = trie[u][i])
      |             ~~^~~~~~~~~~~~
rima.cpp: In function 'int main()':
rima.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |         scanf("%s", s + 1), insert(s);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 308 ms 85356 KB Output is correct
5 Correct 25 ms 3692 KB Output is correct
6 Correct 63 ms 56812 KB Output is correct
7 Correct 59 ms 56556 KB Output is correct
8 Correct 59 ms 56428 KB Output is correct
9 Correct 89 ms 60804 KB Output is correct
10 Correct 59 ms 56556 KB Output is correct