Submission #475386

# Submission time Handle Problem Language Result Execution time Memory
475386 2021-09-22T09:04:58 Z cpp219 Rima (COCI17_rima) C++14
140 / 140
373 ms 134744 KB
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
typedef pair<ld,ll> LD;
const ll N = 5e5 + 9;
const ll mod = 1e9 + 7;
const ll base = 31;

ll n,kq;
string s;

struct Trie{
    Trie *child[26]; ll have = 0,sz = 0;
    void Add(string &s,ll now){
        sz += (now == s.size() - 1);
        if (now == s.size()){
            have = 1; return;
        }
        ll c = s[now] - 'a';
        if (!child[c]) child[c] = new Trie();
        child[c] -> Add(s,now + 1);
    }
    ll GetMax(ll dep){
        priority_queue<ll,vector<ll>,greater<ll>> pq; pq.push(0); pq.push(0);
        for (ll i = 0;i < 26;i++) if (child[i])
            pq.push(child[i] -> GetMax(dep + 1));
        while(pq.size() > 2) pq.pop();
        ll ans = pq.top(),got = (have > 0 || dep == 0); pq.pop();
        //if (sz == 1) debug(got);
        kq = max(kq,(ans + pq.top() + sz + have - (ans > 0) - (pq.top() > 0)));
        kq = max(kq,(pq.top() + sz + have - (pq.top() > 0)));
        //if (kq == 5) debug(sz);
        return (pq.top() + sz + 1 - (pq.top() > 0))*got;
    }
}Tree;

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n;i++){
        cin>>s; reverse(s.begin(),s.end());
        Tree.Add(s,0);
    }
    Tree.GetMax(0);
    cout<<kq;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

rima.cpp: In member function 'void Trie::Add(std::string&, int)':
rima.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         sz += (now == s.size() - 1);
      |                ~~~~^~~~~~~~~~~~~~~
rima.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         if (now == s.size()){
      |             ~~~~^~~~~~~~~~~
rima.cpp: In function 'int main()':
rima.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 373 ms 134744 KB Output is correct
5 Correct 30 ms 1212 KB Output is correct
6 Correct 140 ms 118628 KB Output is correct
7 Correct 126 ms 118468 KB Output is correct
8 Correct 132 ms 118304 KB Output is correct
9 Correct 164 ms 121532 KB Output is correct
10 Correct 129 ms 118292 KB Output is correct