Submission #701254

# Submission time Handle Problem Language Result Execution time Memory
701254 2023-02-20T16:38:03 Z tamthegod Rima (COCI17_rima) C++17
42 / 140
329 ms 229724 KB
// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 3e6 + 5;

const ll oo = 1e18;
int n;
string s[maxN];
int f[maxN];
int res = 0;
void ReadInput()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> s[i];
        reverse(s[i].begin(), s[i].end());
    }
}
struct Trie
{
    struct TNode
    {
        int id;
        int val;
        int mark;
        int child[30];
    };
    vector<TNode> tree;
    void new_node()
    {
        TNode tmp;
        tmp.id = tree.size();
        tmp.val = 0;
        tmp.mark = 0;
        for(int i=0; i<30; i++)
            tmp.child[i] = -1;
        tree.pb(tmp);
    }
    void add(string s)
    {
        int id = 0;
        int cnt = 0;
        for(char c : s)
        {
            cnt++;
            int w = c - 'a';
            if(tree[id].child[w] == -1)
            {
                new_node();
                tree[id].child[w] = tree.size() - 1;
            }
            id = tree[id].child[w];
        }
        tree[id].mark++;
    }
    void dfs(int u)
    {
        vector<int> vc;
        for(int i=0; i<30; i++)
        {
            if(tree[u].child[i] == -1) continue;
            int v = tree[u].child[i];
            dfs(v);
            if(f[v]) vc.pb(f[v]);
            f[u] = max(f[u], f[v]);
        }
        if(vc.empty())
        {
            f[u] = tree[u].mark;
            res = max(res, f[u]);
            return;
        }
        if(tree[u].mark)
        {
            sort(vc.begin(), vc.end(), greater<int>());
            if(vc.size() > 1) res = max(res, vc[0] + vc[1] + tree[u].mark + (int)vc.size() - 2);
            f[u] += tree[u].mark;
            res = max(res, f[u]);
        }
        else f[u] = 0;
    }
};
void Solve()
{
    Trie tree;
    tree.new_node();
    for(int i=1; i<=n; i++)
        tree.add(s[i]);
    tree.dfs(0);
    cout << res;
}
int32_t main()
{
    //freopen("sol.inp", "r", stdin);
    // freopen("sol.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}
# Verdict Execution time Memory Grader output
1 Correct 41 ms 94284 KB Output is correct
2 Correct 41 ms 94292 KB Output is correct
3 Incorrect 41 ms 94352 KB Output isn't correct
4 Incorrect 329 ms 229724 KB Output isn't correct
5 Correct 58 ms 97896 KB Output is correct
6 Incorrect 116 ms 163588 KB Output isn't correct
7 Incorrect 114 ms 163324 KB Output isn't correct
8 Incorrect 119 ms 163116 KB Output isn't correct
9 Incorrect 143 ms 167924 KB Output isn't correct
10 Incorrect 115 ms 163260 KB Output isn't correct