oj.uz

Submission #159890

# Submission time Handle Problem Language Result Execution time Memory
159890 2019-10-25T09:45:52 Z MetB Savez (COCI15_savez) C++14
0 / 120
 230 ms 42972 KB 
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <fstream>
#include <set>
#include <cstring>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <queue>
 
#define N 1000000
 
using namespace std;
 
typedef long long ll;
 
const ll INF = 1e15, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
 
struct Trie {
	struct Node {
		int d;
		map < pair <char, char>, Node* > to;
		bool leaf;

		Node () : d (0), leaf (false) {}
	};

	Node* root = new Node ();

	int add (string s) {
		string t = s;
		reverse (t.begin(), t.end());

		int d = 1;
		Node* x = root;

		for (int i = 0; i < s.length (); i++) {
			if (x -> to.find ({s[i], t[i]}) == x -> to.end ()) {
				x -> to[{s[i], t[i]}] = new Node ();
			}

			x = x -> to[{s[i], t[i]}];
			if (x -> leaf) d = max (d, x -> d + 1);
		}

		x -> leaf = true;
		x -> d = d;

		return d;
	}
} t;

bool comp (const string& a, const string& b) {
	return a.length () < b.length ();
}

int n;

string s[1000000];
 
int main () {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}

	sort (s, s + n, comp);

	int ans = 0;

	for (int i = 0; i < n; i++) {
		ans = max (ans, t.add (s[i]));
	}

	cout << ans;
}

Compilation message

savez.cpp: In member function 'int Trie::add(std::__cxx11::string)':
savez.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.length (); i++) {
                   ~~^~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31736 KB Output is correct
2 Incorrect 28 ms 31736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31736 KB Output is correct
2 Correct 29 ms 31752 KB Output is correct
3 Incorrect 113 ms 42972 KB Output isn't correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 34808 KB Output is correct
2 Incorrect 98 ms 35704 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 33272 KB Output is correct
2 Correct 110 ms 35576 KB Output is correct
3 Incorrect 105 ms 35640 KB Output isn't correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 34864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 34960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 34944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 34424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 32952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 230 ms 33088 KB Output isn't correct
2 Halted 0 ms 0 KB -