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

rima

#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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

140.0 / 140.0

#	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