Submission #735589

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
735589	2023-05-04T11:21:14 Z	vjudge1	Rima (COCI17_rima)	C++17	56 / 140	482 ms	134752 KB

rima

#include <bits/stdc++.h>
using namespace std;
struct Node {
    Node* childs[26];
    int dp;
    bool isleaf = false;
    Node() {
        dp = 0;
        for (auto& child : childs) child = NULL;
    }

    ~Node() {
        for (auto& child : childs) delete child;
    }
};

struct Trie {
    Node* root;
    int max_dp = 0;
    Trie() { root = new Node(); }

    ~Trie() { delete root; }

    void insert(string s) {
        Node* node = root;
        for (const char& c : s) {
            if (node->childs[c - 'a'] == NULL) node->childs[c - 'a'] = new Node();
            node = node->childs[c - 'a'];
        }
        node->isleaf = true;
    }

    int dfs(Node* node) {

        int best = 0, cntLeafs = 0;
        for(char c = 'a' ; c <= 'z' ; ++c) {
            if(node->childs[c - 'a'] != NULL) {
                best = max(best, dfs(node->childs[c - 'a']) - 1);
                cntLeafs += node->childs[c - 'a']->isleaf;
            }
        }
        if(node->isleaf)
            node->dp = cntLeafs + best + 1;
        max_dp = max(max_dp, node->dp);
        max_dp = max(max_dp, cntLeafs + best);
        return node->dp;
    }
};

void solve() {
    int n;
    cin >> n;
    Trie t;
    for(int i = 0 ; i < n ; ++i) {
        string s;
        cin >> s;
        reverse(s.begin(), s.end());
        t.insert(s);
    }

    int tmp = t.dfs(t.root);
    cout << t.max_dp << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        solve();
    }
    return 0;
}

Compilation message

rima.cpp: In function 'void solve()':
rima.cpp:61:9: warning: unused variable 'tmp' [-Wunused-variable]
   61 |     int tmp = t.dfs(t.root);
      |         ^~~

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Incorrect	482 ms	134752 KB	Output isn't correct
5	Correct	12 ms	980 KB	Output is correct
6	Incorrect	103 ms	77604 KB	Output isn't correct
7	Incorrect	102 ms	77524 KB	Output isn't correct
8	Incorrect	105 ms	77344 KB	Output isn't correct
9	Incorrect	123 ms	80472 KB	Output isn't correct
10	Incorrect	123 ms	77312 KB	Output isn't correct