oj.uz

Submission #159896

# Submission time Handle Problem Language Result Execution time Memory
159896 2019-10-25T10:00:38 Z MetB Savez (COCI15_savez) C++14
120 / 120
 287 ms 11388 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 2000000
 
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;
 
int main () {
	cin >> n;

	int ans = 0;

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

	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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 21 ms 11388 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 644 KB Output is correct
2 Correct 69 ms 1440 KB Output is correct
3 Correct 71 ms 1932 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1784 KB Output is correct
2 Correct 70 ms 2060 KB Output is correct
3 Correct 71 ms 1912 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 976 KB Output is correct
2 Correct 71 ms 1912 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 892 KB Output is correct
2 Correct 79 ms 1912 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 888 KB Output is correct
2 Correct 86 ms 2044 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 1016 KB Output is correct
2 Correct 89 ms 2812 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 376 KB Output is correct
2 Correct 120 ms 1508 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 256 KB Output is correct
2 Correct 154 ms 1636 KB Output is correct
3 Correct 287 ms 2312 KB Output is correct