Submission #743682

#	Time	Username	Problem	Language	Result	Execution time	Memory
743682		vjudge1	Rima (COCI17_rima)	C++17	28 / 140	420 ms	125076 KiB

rima

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 5, M = 3e6 + 6, mod = 998244353;
const int K = 26;
int dp[M];

struct Vertex {
    int next[K];

    Vertex() {
        fill(begin(next), end(next), -1);
    }
};


vector<Vertex> t(1);

pair<int, int> add_string(string const &s) {
    int v = 0, curDep = 0;
    int parent = 0;
    for (char ch: s) {
        int c = ch - 'a';
        if (t[v].next[c] == -1) {
            t[v].next[c] = t.size();
            t.emplace_back();
        }
        parent = v;
        v = t[v].next[c];
    }
    return {v, parent};
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<string> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        reverse(v[i].begin(), v[i].end());
    }
    sort(v.begin(), v.end(), [&](auto a, auto b) {
        return a.size() < b.size();
    });
    for (int i = 0; i < n; ++i) {
    pair<int, int> p = add_string(v[i]);
    int idx = p.first;
    int par = p.second;
    int mx = 0;
    for (int j = 0; j < K; ++j) { // me with same size equal me
        if (t[par].next[j] != -1) {
            mx = max(mx, dp[t[par].next[j]] + 1);
        }
    }
    mx = max(mx, dp[par] + 1);// me with size less than me by 1
    for (int j = 0; j < K; ++j) { // me with size greater than me by 1
        if (t[idx].next[j] != -1) {
            mx = max(mx, dp[t[idx].next[j]] + 1);
        }
    }
    dp[idx] = mx;
}

cout << *
max_element(dp, dp
+ M) << '\n';
}

Compilation message (stderr)

rima.cpp: In function 'std::pair<int, int> add_string(const string&)':
rima.cpp:23:16: warning: unused variable 'curDep' [-Wunused-variable]
   23 |     int v = 0, curDep = 0;
      |                ^~~~~~

• Subtask 1: 28 / 140