oj.uz

답안 #696320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
696320 2023-02-06T08:17:50 Z uylulu Rima (COCI17_rima) C++14
126 / 140
 324 ms 116008 KB 
#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

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.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 47300 KB Output is correct
2 Correct 17 ms 47316 KB Output is correct
3 Correct 17 ms 47316 KB Output is correct
4 Incorrect 324 ms 115768 KB Output isn't correct
5 Correct 33 ms 48516 KB Output is correct
6 Correct 99 ms 114060 KB Output is correct
7 Correct 101 ms 114024 KB Output is correct
8 Correct 101 ms 113744 KB Output is correct
9 Correct 117 ms 116008 KB Output is correct
10 Correct 104 ms 113692 KB Output is correct