Submission #743675

#	Time	Username	Problem	Language	Result	Execution time	Memory
743675		vjudge1	Rima (COCI17_rima)	C++17	14 / 140	284 ms	125612 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());
        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: 14 / 140