oj.uz

Submission #208030

# Submission time Handle Problem Language Result Execution time Memory
208030 2020-03-09T20:04:42 Z mkisic Rima (COCI17_rima) C++14
56 / 140
 1000 ms 217848 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 152952 KB Output is correct
2 Correct 102 ms 152952 KB Output is correct
3 Correct 102 ms 152952 KB Output is correct
4 Execution timed out 1110 ms 217848 KB Time limit exceeded
5 Correct 251 ms 159096 KB Output is correct
6 Incorrect 142 ms 155260 KB Output isn't correct
7 Incorrect 132 ms 155000 KB Output isn't correct
8 Incorrect 126 ms 154744 KB Output isn't correct
9 Incorrect 284 ms 162148 KB Output isn't correct
10 Incorrect 127 ms 154736 KB Output isn't correct