oj.uz

Submission #242134

# Submission time Handle Problem Language Result Execution time Memory
242134 2020-06-27T00:29:06 Z ant101 Rima (COCI17_rima) C++14
140 / 140
 501 ms 56440 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define REP(i, n) for (int i=0; i<n; i++)
#define FOR(i, a, b) for (int i=(a); i<(b); i++)

typedef long long ll;
typedef pair<int, int> P;
#define X first
#define Y second

const int MAX = 3000100;

struct node {
    int br, dp;
    vector <pair<char, node*> > V;
    node() {
        br = dp = 0;
        V.clear();
    }
} *root;

char s[MAX];
int rje = 0;

void insert()
{
    int len = (int) strlen(s);
    node *tmp = root;
    REP(i, len) {
        node *nov = 0;
        for (auto it : tmp->V)
            if (it.X == s[i]) {
                nov = it.Y;
                break;
            }
        
        if (!nov) {
            nov = new node;
            tmp->V.push_back({s[i], nov});
        }
        tmp = nov;
    }
    
    tmp->br = 1;
}

void dfs(node *p)
{
    P mx{0, 0};
    int ima = 0;
    
    for (auto it : p->V) {
        dfs(it.Y);
        ima += it.Y->br;
        mx = max(mx, P(mx.X, it.Y->dp));
        mx = max(mx, P(it.Y->dp, mx.X));
        
        p->dp = max(p->dp, it.Y->dp);
    }
    
    if (p->br) p->dp += 1 + max(0, ima-1);
    else p->dp = 0;
    
    rje = max(rje, mx.X + mx.Y + p->br + max(0, ima - 2));
}

int main()
{
    root = new node;
    int n;
    cin >> n;
    REP(i, n) {
        cin >> s;
        reverse(s, s + strlen(s));
        insert();
    }
    dfs(root);
    cout << rje << endl;
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 501 ms 48120 KB Output is correct
5 Correct 146 ms 3576 KB Output is correct
6 Correct 82 ms 53112 KB Output is correct
7 Correct 77 ms 52984 KB Output is correct
8 Correct 74 ms 52812 KB Output is correct
9 Correct 224 ms 56440 KB Output is correct
10 Correct 74 ms 52856 KB Output is correct