답안 #735582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
735582	2023-05-04T11:15:43 Z	vjudge1	Rima (COCI17_rima)	C++17	56 / 140	494 ms	137480 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, max(0, 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);
        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:60:9: warning: unused variable 'tmp' [-Wunused-variable]
   60 |     int tmp = t.dfs(t.root);
      |         ^~~

Subtask #1

56.0 / 140.0

#	결과	실행 시간	메모리	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	494 ms	137480 KB	Output isn't correct
5	Correct	15 ms	3712 KB	Output is correct
6	Incorrect	101 ms	78196 KB	Output isn't correct
7	Incorrect	105 ms	77972 KB	Output isn't correct
8	Incorrect	103 ms	77788 KB	Output isn't correct
9	Incorrect	119 ms	83452 KB	Output isn't correct
10	Incorrect	97 ms	77784 KB	Output isn't correct