Submission #735588

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
735588	2023-05-04T11:20:28 Z	vjudge1	Rima (COCI17_rima)	C++17	0 / 140	2 ms	340 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);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#else
#endif
    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);
      |         ^~~
rima.cpp: In function 'int main()':
rima.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	340 KB	Output isn't correct
2	Incorrect	2 ms	340 KB	Output isn't correct
3	Incorrect	2 ms	340 KB	Output isn't correct
4	Incorrect	2 ms	340 KB	Output isn't correct
5	Incorrect	2 ms	340 KB	Output isn't correct
6	Incorrect	2 ms	340 KB	Output isn't correct
7	Incorrect	2 ms	340 KB	Output isn't correct
8	Incorrect	2 ms	340 KB	Output isn't correct
9	Incorrect	2 ms	340 KB	Output isn't correct
10	Incorrect	2 ms	340 KB	Output isn't correct