Submission #1126876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126876		chenwz	Rima (COCI17_rima)	C++20	140 / 140	170 ms	67652 KiB

rima

// COCI 2016/2017 Contest 4 Rima
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
const int SZ = 3e6 + 4, SG = 26;
int sz = 1, W[SZ], D[SZ], ch[SZ][SG];
void insert(const string &s) {  // Trie插入字符串s
  int u = 0;
  for (char c : s) {
    int &v = ch[u][c - 'a'];
    if (!v) v = sz++;
    u = v;
  }
  W[u] = 1;  // u点对应单词结尾
}  // D[u]:从u开始一路向右或者向下的最长链(必须路过单词点)
void dfs(int u, int &ans) {
  int wv = 0, mx = 0, mx1 = 0;  // wv: u的儿子中单词节点的个数
  _for(i, 0, SG) if (ch[u][i]) {
    int v = ch[u][i], &dv = D[v];
    dfs(v, ans), wv += W[v];
    if (mx < dv)
      mx1 = mx, mx = dv;
    else if (mx1 < dv)
      mx1 = dv;
  }
  if (W[u]) D[u] = mx + max(wv, 1);
  ans = max(ans, mx + mx1 + W[u] + max(wv - 2, 0));
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, ans = 0;
  cin >> n;
  string s;
  for (int i = 0; i < n and cin >> s; i++) reverse(begin(s), end(s)), insert(s);
  dfs(0, ans), printf("%d\n", ans);
  return 0;
}

• Subtask 1: 140 / 140