답안 #701246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701246 2023-02-20T16:14:03 Z tamthegod Rima (COCI17_rima) C++17
56 / 140
269 ms 262144 KB
// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define int long long
#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 = 1e6 + 5;
const int mod = (int)1e14 + 7;
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;
            }
            if(cnt == s.size()) tree[id].val++;
            id = tree[id].child[w];
        }
        tree[id].mark++;
    }
    void dfs(int u)
    {
        for(int i=0; i<30; i++)
        {
            if(tree[u].child[i] == -1) continue;
            int v = tree[u].child[i];
            dfs(v);
            f[u] += f[v];
        }
        if(tree[u].mark) f[u] += tree[u].mark;
        else f[u] = 0;
        res = max(res, f[u]);
    }
};
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();
}
// 1 1 2 3 4 5 1 1 2 6 2 3 4 7 5 1 1 1
// 1 1 2 3 4 5 1 6 7 8 2 3 4 9 5 1 1 1

Compilation message

rima.cpp: In member function 'void Trie::add(std::string)':
rima.cpp:63:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             if(cnt == s.size()) tree[id].val++;
      |                ~~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31828 KB Output is correct
2 Correct 17 ms 31828 KB Output is correct
3 Correct 18 ms 31784 KB Output is correct
4 Runtime error 269 ms 262144 KB Execution killed with signal 9
5 Correct 31 ms 35776 KB Output is correct
6 Incorrect 146 ms 167940 KB Output isn't correct
7 Incorrect 138 ms 167924 KB Output isn't correct
8 Incorrect 142 ms 167832 KB Output isn't correct
9 Incorrect 168 ms 170572 KB Output isn't correct
10 Incorrect 143 ms 167796 KB Output isn't correct