# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
208025 | mkisic | Rima (COCI17_rima) | C++14 | 1076 ms | 220688 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |