Submission #1084071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084071		pndhpndh	Rima (COCI17_rima)	C++14	56 / 140	388 ms	162720 KiB

rima

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pb push_back
int n, m;
const int mx=1e6+5;
const int inf=1e18;
int dp[mx];
void read(){

}
struct Trie{
    struct Trie* child[26]; int cnt;int ed;
};
Trie* Node(){
    struct Trie* root = NULL;
    root = (Trie*)malloc(sizeof(struct Trie));
    for(int i=0;i<=25;i++) root->child[i] = NULL;
    root->cnt = -1;
    return root;
}
int res=1;
void addstr(Trie* root, string s){
    for(int i=0;i+1<s.size();i++){
        char f=s[i];
        int c = f - 'a';
        if(root->child[c] == NULL){
            root->child[c] = Node();
        }
        root = root->child[c];
    }
    if (root->cnt==-1){
        root->cnt=0;
    }
    char f=s[s.size()-1];
    int c = f - 'a';
    if(root->child[c] == NULL){
        root->child[c] = Node();
    }
    root = root->child[c];
    root->cnt=1;
    // cout << root->cnt << '\n';
}
int dfs(Trie* root){
    int ans=root->cnt;
    // cout << ans << '\n';
    for (int i=0;i<=25;i++){
        Trie* temp=root;
        if (root->child[i]!=NULL){
            temp=temp->child[i];
            // cout << (char)(i+'a') << " ";
            int a=dfs(temp);
            // cout << ans << " " << a << " " << (char)(i+'a') << '\n';
            if (temp->cnt==1){
                ans+=a;
            }
            // cout << ans << " " << a << " " << (char)(i+'a') << '\n';
        }
    }
    res=max(res,ans);
    // std::cout << ans << '\n';
    return ans;
}
bool cmp(string a,string b){
    if (a.size()==b.size()){
        for (int i=0;i<a.size();i++){
            if (a[i]!=b[i]){
                return a[i]<b[i];
            }
        }
    }
    return a.size()<b.size();
}
void solve(){
    int n;
    cin >> n;
    string s;
    Trie* root = Node();
    vector<string> vect;
    root->cnt=0;
    for (int i=1;i<=n;i++){
        cin >> s;
        reverse(s.begin(),s.end());
        vect.pb(s);
    }
    sort(vect.begin(),vect.end(),cmp);
    vect.erase(unique(vect.begin(),vect.end()),vect.end());
    for (int i=0;i<vect.size();i++){
        addstr(root,vect[i]);
    }
    dfs(root);
    cout << res;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    read();
    solve();
    return 0;
}

Compilation message (stderr)

rima.cpp: In function 'void addstr(Trie*, std::string)':
rima.cpp:24:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i+1<s.size();i++){
      |                 ~~~^~~~~~~~~
rima.cpp: In function 'bool cmp(std::string, std::string)':
rima.cpp:66:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int i=0;i<a.size();i++){
      |                      ~^~~~~~~~~
rima.cpp: In function 'void solve()':
rima.cpp:88:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i=0;i<vect.size();i++){
      |                  ~^~~~~~~~~~~~

• Subtask 1: 56 / 140