oj.uz

답안 #475378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
475378 2021-09-22T08:55:22 Z cpp219 Rima (COCI17_rima) C++14
84 / 140
 423 ms 135692 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 && now);
        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 + got - (ans > 0) - (pq.top() > 0)));
        kq = max(kq,(pq.top() + sz + got - (pq.top() > 0)));
        if (kq == 5) debug(pq.top());
        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 && now);
      |                ~~~~^~~~~~~~~~~~~~~
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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
rima.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
84.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Incorrect 423 ms 135692 KB Output isn't correct
5 Incorrect 24 ms 2876 KB Output isn't correct
6 Correct 130 ms 119244 KB Output is correct
7 Correct 132 ms 119008 KB Output is correct
8 Incorrect 42 ms 67104 KB Output isn't correct
9 Correct 166 ms 122648 KB Output is correct
10 Correct 131 ms 118736 KB Output is correct