oj.uz

Submission #95169

# Submission time Handle Problem Language Result Execution time Memory
95169 2019-01-27T20:46:10 Z frodakcin Rima (COCI17_rima) C++11
140 / 140
 418 ms 67704 KB 
#include <iostream>
#include <cstdio>

using namespace std;

template<class T> void mx(T& a, const T& b) {if(a < b) a = b;}
void f2(int * x, int v) {
  for(int i = 0;i < 2;i++) if(v > x[i]) swap(v, x[i]);
}

const int MN = 5e5 + 100;
const int ML = 3e6 + 1000;

#define ci(X) (static_cast<int>(X) - 97)

char I[ML];
template<int MS = ML> struct TRIE {
public:
  int c[MS][26], v[MS], d[MS];
  int X, R;
  int nn() {
    for(int i = 0;i < 26;i++) c[X][0] = 0;
    v[X] = d[X] = 0;
    return X++;
  }
  TRIE() : X(0) {nn(), R = nn();}
  void add(char * s) {
    int n = R;
    for(int i = 0, j;s[i] != '\0';i++) if(c[n][j = ci(s[i])]) n = c[n][j]; else n = c[n][j] = nn();
    v[n]++;
  }
  void dfs(int n, int& f) {
    int h[2] = {0, 0}, z = 0;
    for(int i = 0;i < 26;i++) if(c[n][i]) dfs(c[n][i], f), z += v[c[n][i]];
    for(int i = 0;i < 26;i++) if(c[n][i] and v[c[n][i]]) mx(d[n], d[c[n][i]] + z), f2(h, d[c[n][i]]);
    mx(f, h[0] + h[1] + z + v[n]);
  }
  int build() {
    int f = 0;
    dfs(R, f);
    return f;
  }
};
TRIE<> trie;

int N;

int main() {
  scanf("%d", &N);
  for(int i = 0, l;i < N;i++) {
    scanf(" %s", I);
    for(l = 0;I[l] != 0;l++);
    for(int j = 0;j < l>>1;j++) swap(I[j], I[l-j-1]);
    trie.add(I);
  }
  printf("%d\n", trie.build());
  return 0;
}

Compilation message

rima.cpp: In function 'int main()':
rima.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
rima.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", I);
     ~~~~~^~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 418 ms 67704 KB Output is correct
5 Correct 32 ms 632 KB Output is correct
6 Correct 85 ms 45820 KB Output is correct
7 Correct 81 ms 45728 KB Output is correct
8 Correct 83 ms 45660 KB Output is correct
9 Correct 112 ms 47352 KB Output is correct
10 Correct 83 ms 45852 KB Output is correct