Submission #696320

#	Time	Username	Problem	Language	Result	Execution time	Memory
696320		uylulu	Rima (COCI17_rima)	C++14	126 / 140	324 ms	116008 KiB

rima

#include<bits/stdc++.h>
using namespace std;

// #define int long long
#define endl "\n"

const int N = 5e5,sz = 6e6;

struct vertex{
    int nxt[26],pa = -1;
    bool spec = false;
    vertex() {
        memset(nxt,-1,sizeof(nxt));
    }
};

vector<vertex> trie(1);

void add(string s) {
    int v = 0,lst;
    for(auto u : s) {
        int c = u - 'a';
        if(trie[v].nxt[c] == -1) {
            trie[v].nxt[c] = trie.size();
            trie.emplace_back();
        }
        lst = v;
        v = trie[v].nxt[c];
        // cout<<lst<<" "<<v<<" "<<u<<endl;
    } 
    trie[v].spec = true;
}

int dp[sz + 1],one[sz + 1];

inline void dfs(int s) {
    if(dp[s] != -1) return;

    one[s] = 0;
    dp[s] = 0;

    int sz = 0;
    for(int i = 0;i < 26;i++) {
        int u = trie[s].nxt[i];
        if(u != -1) {
            dfs(u);
        }

        if(u != -1 && trie[u].spec) {
            sz++;
        }
    }
    if(trie[s].spec) {
        one[s] += trie[s].spec;
        one[s] += sz;

        int len = 0;

        for(int i = 0;i < 26;i++) {
            int u = trie[s].nxt[i];

            if(u != -1) {
                len = max(len,one[u]);
            }
        }
        if(len > 0) {
            one[s] += (len - 1);
        }
    }

    int cnt = 0;

    vector<int> st;

    for(int i = 0;i < 26;i++) {
        int u = trie[s].nxt[i];

        if(u != - 1) {
            st.push_back(one[u]);
        }
    }
    sort(st.begin(),st.end(),greater<int>());

    int tru = 0;

    for(int i = 0;i < 2 && i < st.size();i++) {
        dp[s] += (st[i] - 1);
    }
    dp[s] += trie[s].spec;
    dp[s] += sz;
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);

    int n;
    cin>>n;
    for(int i = 1;i <= n;i++) {
        string tmp;
        cin>>tmp;

        reverse(tmp.begin(),tmp.end());
        
        add(tmp);
    }
    int len = trie.size();

    memset(dp,-1,sizeof(dp));
    memset(one,-1,sizeof(one));

    dfs(0);

    int kq = 0;
    for(int i = 1;i <= trie.size();i++) {
        kq = max(kq,dp[i]);
        kq = max(kq,one[i]);
    }
    cout<<kq<<endl;


}           

Compilation message (stderr)

rima.cpp: In function 'void add(std::string)':
rima.cpp:20:15: warning: variable 'lst' set but not used [-Wunused-but-set-variable]
   20 |     int v = 0,lst;
      |               ^~~
rima.cpp: In function 'void dfs(int)':
rima.cpp:86:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i = 0;i < 2 && i < st.size();i++) {
      |                            ~~^~~~~~~~~~~
rima.cpp:71:9: warning: unused variable 'cnt' [-Wunused-variable]
   71 |     int cnt = 0;
      |         ^~~
rima.cpp:84:9: warning: unused variable 'tru' [-Wunused-variable]
   84 |     int tru = 0;
      |         ^~~
rima.cpp: In function 'int main()':
rima.cpp:117:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i = 1;i <= trie.size();i++) {
      |                   ~~^~~~~~~~~~~~~~
rima.cpp:109:9: warning: unused variable 'len' [-Wunused-variable]
  109 |     int len = trie.size();
      |         ^~~

• Subtask 1: 126 / 140