Submission #736165

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
736165	2023-05-05T09:13:13 Z	marvinthang	Rima (COCI17_rima)	C++17	140 / 140	278 ms	137348 KB

rima

/******************************
*    author : @marvinthang    *
*    date : 09 / 02 / 2022    *
******************************/

#include <bits/stdc++.h>

using namespace std;

#define  superspeed  ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
#define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class U, class V> ostream & operator << (ostream& out, const pair<U, V> &p) { return out << '(' << p.first << ", " << p.second << ')'; }
template <class T> ostream & operator << (ostream &out, const vector<T> &vt) { out << '{'; for (size_t i = 0; i + 1 < vt.size(); i++) out << vt[i] << ", "; if (!vt.empty()) out << vt.back(); return out << '}'; }

const 		int MOD = 1e9 + 7;
const     double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const     int dir[] = {0, 1, 0, -1, 0}; // {0, 1, 1, -1, -1, 1, 0, -1, 0};
const  long long oo = 1e18;
const       int MAX = 1e5 + 5;

bool update(pair <int, int> &x, const int &y) {
	if (x.first < y) {
		x.second = x.first;
		x.first = y;
		return true;
	}
	x.second = max(x.second, y);
	return false;
}

int res;

struct Trie {

	static const int ALPHABET_SIZE = 26;
	static const int capital = 'a';

	struct Node {

		Node *child[ALPHABET_SIZE];
		int numLeaf, F;

		Node() {
			for (int i = 0; i < ALPHABET_SIZE; ++i) child[i] = nullptr;
			numLeaf = 0;
			F = 0;
		}

	};

	Node *root;

	Trie() { root = new Node(); }

	void insert(const string &s) {
		int n = s.size();
		Node *p = root;
		for (int i = 0; i < n; ++i) {
			int nxt = s[i] - capital;
			if (p -> child[nxt] == nullptr)
				p -> child[nxt] = new Node();
			p = p -> child[nxt];
		}
		++p -> numLeaf;
	}

	bool erase(const string &s) {
		int n = s.size();
		Node *p = root;
		for (int i = 0; i < n; ++i) {
			int nxt = s[i] - capital;
			if (p -> child[nxt] == nullptr) return false;
			p = p -> child[nxt];
		}
		--p -> numLeaf;
		return true;
	}

	void dp(Node *p) {
		pair <int, int> cur = make_pair(0, 0);
		int cnt = 0;
		for (int nxt = 0; nxt < ALPHABET_SIZE; ++nxt) {
			if (p -> child[nxt] == nullptr) continue;
			Node *child = p -> child[nxt];
			dp(child);
			cnt += child -> numLeaf;
			update(cur, child -> F);
			p -> F = max(p -> F, child -> F);
		}
		if (p -> numLeaf) p -> F += 1 + max(0, cnt - 1);
		else p -> F = 0;

		res = max(res, cur.first + cur.second + p -> numLeaf + max(0, cnt - 2));
	}

} Tree;

int N;

int main(void) {
    superspeed;
    file("coci1617_r4_rima");
    cin >> N;
    for (int i = 1; i <= N; ++i) {
    	string s; cin >> s;
    	reverse(s.begin(), s.end());
    	Tree.insert(s);
    }
    Tree.dp(Tree.root);
    cout << res << '\n';
    return 0;
}

Compilation message

rima.cpp: In function 'int main()':
rima.cpp:11:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rima.cpp:103:5: note: in expansion of macro 'file'
  103 |     file("coci1617_r4_rima");
      |     ^~~~
rima.cpp:11:95: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
rima.cpp:103:5: note: in expansion of macro 'file'
  103 |     file("coci1617_r4_rima");
      |     ^~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	352 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	278 ms	137348 KB	Output is correct
5	Correct	14 ms	3668 KB	Output is correct
6	Correct	70 ms	79740 KB	Output is correct
7	Correct	70 ms	79340 KB	Output is correct
8	Correct	71 ms	79104 KB	Output is correct
9	Correct	91 ms	84784 KB	Output is correct
10	Correct	68 ms	79140 KB	Output is correct