oj.uz

Submission #208025

# Submission time Handle Problem Language Result Execution time Memory
208025 2020-03-09T19:54:23 Z mkisic Rima (COCI17_rima) C++14
28 / 140
 1000 ms 220688 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) + 1);
  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];
    }
  }

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

  return 0;
}

Subtask #1
28.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 152952 KB Output isn't correct
2 Correct 93 ms 153080 KB Output is correct
3 Incorrect 94 ms 152952 KB Output isn't correct
4 Execution timed out 1076 ms 220688 KB Time limit exceeded
5 Correct 241 ms 161880 KB Output is correct
6 Incorrect 129 ms 155900 KB Output isn't correct
7 Incorrect 120 ms 155516 KB Output isn't correct
8 Incorrect 118 ms 155252 KB Output isn't correct
9 Incorrect 277 ms 165152 KB Output isn't correct
10 Incorrect 119 ms 155260 KB Output isn't correct