# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
701222 | Do_you_copy | Rima (COCI17_rima) | C++17 | 342 ms | 205100 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int maxN = 3e6 + 10;
const int inf = 0x3f3f3f3f;
int n;
string s[maxN];
struct TNode{
int a[26];
bool ok;
TNode(){
memset(a, 0, sizeof(a));
ok = 0;
}
};
vector <TNode> S(1);
int dp[maxN];
void add(int id, int cur, int pos){
if (pos == signed(s[cur].length())){
S[id].ok = 1;
return;
}
if (!S[id].a[s[cur][pos] - 'a']){
S[id].a[s[cur][pos]- 'a'] = S.size();
S.pb(TNode());
}
add(S[id].a[s[cur][pos] - 'a'], cur, pos + 1);
}
int ans = 0;
void dfs(int u){
pii maxx = {0, 0};
int sum = S[u].ok;
int cnt = 0;
for (int i = 0; i < 26; ++i){
if (S[u].a[i]){
dfs(S[u].a[i]);
sum += dp[S[u].a[i]];
cnt += bool(dp[S[u].a[i]]);
if (maxx.fi < dp[S[u].a[i]]){
swap(maxx.fi, maxx.se);
maxx.fi = dp[S[u].a[i]];
}
else{
maxx.se = max(maxx.se, dp[S[u].a[i]]);
}
}
}
if (S[u].ok){
ans = max(ans, sum);
dp[u] = sum;
}
else{
ans = max(ans, maxx.fi + maxx.se + max(0, cnt - 2));
}
}
void Init(){
cin >> n;
for (int i = 1; i <= n; ++i){
cin >> s[i];
reverse(s[i].begin(), s[i].end());
add(0, i, 0);
}
dfs(0);
cout << ans;
}
#define taskname "test"
signed main(){
if (fopen(taskname ".inp", "r")){
freopen(taskname ".inp", "r", stdin);
freopen(taskname ".out", "w", stdout);
}
int tt = 1;
//cin >> tt;
while (tt--){
Init();
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |