# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
93959 | updown1 | Rima (COCI17_rima) | C++17 | 1088 ms | 68728 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.
/*
The length decreases and then increases
for every node, count everything with the same suffix
dp[node] = (increasing sequence) max length sequence starting from this node ( but not counting count[node] or this node )
try every length as the smallest length
answer is max(big1[len]+big2[len]+count[word] where big1 an big2 have the same suffix)
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=500000, INF=1000000000;
///500,000,000
int N, dp[MAXN], out;
string inp[MAXN];
bool vis[MAXN];
map<string, vector<int> > cnt; /// (suffix, vector<index> )
void go(int at) {
if (vis[at]) return;
vis[at] = true;
for (int i: cnt[inp[at]]) {
go(i);
dp[at] = max(dp[at], dp[i]+(int)cnt[inp[at]].size());
}
//w<< inp[at] s (int)(cnt[inp[at]].size())<<e;
}
main() {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
ffi {
cin >> inp[i];
cnt[inp[i].substr(1)].pb(i);
}
ffi go(i);
//ffi w<< inp[i] c dp[i]<<e;
ffi vis[i] = false;
ffi if (!vis[i]) {
string use = inp[i].substr(1);
int big1 = 0, big2 = 0;
for (int j: cnt[use]) {
big2 = max(big2, dp[j]);
if (big2 > big1) swap(big2, big1);
vis[j] = true;
}
out = max(out, big1+big2+(int)cnt[use].size());
}
w<< out<<e;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |