oj.uz

Submission #897648

# Submission time Handle Problem Language Result Execution time Memory
897648 2024-01-03T14:17:24 Z mihtriii295 Rima (COCI17_rima) C++17
14 / 140
 255 ms 46052 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>

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 * 2 + p->br + max(0, ima - 2));
}

int main()
{
  root = new node;

  int n;
  scanf("%d", &n);
  REP(i, n) {
    scanf("%s", s);
    reverse(s, s + strlen(s));
    insert();
  }

  dfs(root);
  printf("%d\n", rje);

  return 0;
}

Compilation message

rima.cpp: In function 'int main()':
rima.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
rima.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%s", s);
      |     ~~~~~^~~~~~~~~

Subtask #1
14.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Correct 255 ms 45684 KB Output is correct
5 Incorrect 15 ms 604 KB Output isn't correct
6 Incorrect 43 ms 44888 KB Output isn't correct
7 Incorrect 44 ms 44880 KB Output isn't correct
8 Incorrect 40 ms 44880 KB Output isn't correct
9 Incorrect 63 ms 46052 KB Output isn't correct
10 Incorrect 40 ms 44880 KB Output isn't correct