Submission #1105832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105832		nh0902	Rima (COCI17_rima)	C++14	126 / 140	190 ms	123504 KiB

rima

#include <bits/stdc++.h>

using namespace std;

const int N = 500010, M = 3000010;

int n;

string s[N];

vector<pair<char, int>> child[M];
bool is_present[M];
int cur;

void add(string s) {
    int pos = 0;
    for (char c : s) {
        int not_child = true;
        int next = 0;
        for (pair<char, int> p : child[pos]) {
            if (p.first == c) {
                not_child = false;
                next = p.second;
                break;
            }
        }
        if (not_child) {
            cur ++;
            next = cur;
            child[pos].push_back({c, next});
        }
        pos = next;
    }
    is_present[pos] = true;
}

int ans;

int dfs(int u) {
    int max_path = 0;
    int max_path2 = 0;
    int cnt_present_child = 0;
    for (pair<char, int> p : child[u]) {
        max_path2 = max(max_path2, dfs(p.second));
        if (max_path2 > max_path) {
            swap(max_path, max_path2);
        }
        if (is_present[p.second]) {
            cnt_present_child ++;
        }
    }
    //cout << u << " : " << max_path << " , " << max_path2 << "\n";

    if (!is_present[u]) {
        return 0;
    }
    if (cnt_present_child >= 2) {
        ans = max(ans, max_path + max_path2 + cnt_present_child - 1);
    }
    else {
        ans = max(ans, max_path + 1);
    }
    //ans = max(ans, max_path + cnt_present_child);
    //cout << u << " : " << height + height2 + 1 << "\n";
    if (cnt_present_child <= 1) {
        //cout << u << " : " << max_path + 1 << "\n";
        return max_path + 1;

    }
    //cout << u << " : " << max_path + cnt_present_child << "\n";
    return max_path + cnt_present_child;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    for (int i = 1; i <= n; i ++) {
        cin >> s[i];
        reverse(s[i].begin(), s[i].end());
        add(s[i]);

     }

    dfs(0);

    cout << ans;
    return 0;
}

• Subtask 1: 126 / 140