Submission #208030

#	Time	Username	Problem	Language	Result	Execution time	Memory
208030		mkisic	Rima (COCI17_rima)	C++14	56 / 140	1110 ms	217848 KiB

rima

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair
#define pb push_back

const int MAXN = 3000005;

int n;
string s;

vector <string> v[MAXN];
unordered_map <string, int> ime, kanter;
int cnt[MAXN];
int IME;

vector <int> E[MAXN];

void add_edge(int a, int b) {
  E[a].pb(b);
}

int dp[MAXN];

int rek(int cvor) {
  if (dp[cvor] != -1) return dp[cvor];
  int ret = cnt[cvor];
  for (auto ncvor : E[cvor]) ret = max(ret, rek(ncvor) + cnt[cvor]);
  return dp[cvor] = ret;
}

int main() {
  cin >> n;
  REP(i, n) {
    cin >> s;
    ime[s] = ++IME;
    v[(int)s.size()].pb(s);
    add_edge(0, IME);
  }

  REP(i, MAXN - 1) {
    if (v[i].empty()) continue;
    kanter.clear();
    for (auto s : v[i]) {
      string t = s.substr(1, (int)s.size() - 1);
      if (ime.count(t)) add_edge(ime[t], ime[s]);
      kanter[t]++;
    }
    for (auto s : v[i]) {
      string t = s.substr(1, (int)s.size() - 1);
      cnt[ime[s]] = kanter[t];
    }
  }

  cnt[0] = 1;
  memset(dp, -1, sizeof dp);
  printf("%d\n",rek(0) - 1);

  return 0;
}

• Subtask 1: 56 / 140