제출 #735582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
735582		vjudge1	Rima (COCI17_rima)	C++17	56 / 140	494 ms	137480 KiB

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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 140