Submission #159890

#	Time	Username	Problem	Language	Result	Execution time	Memory
159890		MetB	Savez (COCI15_savez)	C++14	0 / 120	230 ms	42972 KiB

savez

#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 (stderr)

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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12