Submission #95167

#TimeUsernameProblemLanguageResultExecution timeMemory
95167frodakcinRima (COCI17_rima)C++11
126 / 140
1089 ms175848 KiB
#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 S = ML> struct TRIE { public: int c[MN][26], v[MN], d[MN]; 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;s[i] != '\0';i++) if(c[n][ci(s[i])]) n = c[n][ci(s[i])]; else n = c[n][ci(s[i])] = 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);
     ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...