Submission #95169

#	Time	Username	Problem	Language	Result	Execution time	Memory
95169		frodakcin	Rima (COCI17_rima)	C++11	140 / 140	418 ms	67704 KiB

rima

#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 (stderr)

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 / 140