Submission #1105830

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1105830	2024-10-28T03:26:35 Z	nh0902	Rima (COCI17_rima)	C++14	0 / 140	393 ms	135996 KB

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

0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	32 ms	87112 KB	Output isn't correct
2	Incorrect	33 ms	87132 KB	Output isn't correct
3	Incorrect	35 ms	87136 KB	Output isn't correct
4	Incorrect	393 ms	116480 KB	Output isn't correct
5	Incorrect	51 ms	93256 KB	Output isn't correct
6	Incorrect	121 ms	130556 KB	Output isn't correct
7	Incorrect	121 ms	130260 KB	Output isn't correct
8	Incorrect	134 ms	130156 KB	Output isn't correct
9	Incorrect	158 ms	135996 KB	Output isn't correct
10	Incorrect	121 ms	130176 KB	Output isn't correct