Submission #95175

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
95175	2019-01-27T21:35:38 Z	Pusheen	Rima (COCI17_rima)	C++11	140 / 140	464 ms	228752 KB

rima

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<double, double> pd;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;

template<class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;

template<class T, class U>
inline void MAX(T &a, U b) { if (a < b) a = b; }

template<class T, class U>
inline void MIN(T &a, U b) { if (a > b) a = b; }

template<class T, class U>
inline void MODA(T &a, U b) {
	a %= b;
	if (a < 0) a += b;
}

#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(20)
#define dbg(x) cout << (#x) << " is " << (x) << '\n'
#define dbg2(x, y) cout << (#x) << " is " << (x) << " and " << (#y) << " is " << y << '\n'
#define dbgarr(x, sz) for(int asdf = 0; asdf < (sz); asdf++) cout << x[asdf] << ' '; cout << '\n'
#define dbgarr2(x, rose, colin) for(int asdf2 = 0; asdf2 < rose; asdf2++) { dbgarr(x[asdf2], colin); }
#define dbgitem(x) for(auto asdf = x.begin(); asdf != x.end(); asdf++) cout << *asdf << ' '; cout << '\n'
#define finish(x) return cout << (x) << '\n', 0
#define F0R(i, a) for(int (i)=0;(i)<(a);++(i))
#define FOR(i, a, b) for(int (i)=(a);(i)<(b);++(i))
#define F0Rd(i, a) for(int (i)=a;(i)>=0;--(i))
#define FORd(i, a, b) for(int (i)=a;(i)>=(b);--(i))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

template <typename T> ostream& operator<<(ostream& os, const vector<T> &p){os << "["; F0R(i, p.size()) os << p[i] << (i == p.size() - 1 ? "" : ",") ; os << "]"; return os;}
template <typename T> ostream& operator<<(ostream& os, const set<T> &p){os << "{ "; for (T x: p) os << x << " "; os << "}"; return os;}
template <typename T> ostream& operator<<(ostream& os, const multiset<T> &p){os << "{ "; for (T x: p) os << x << " "; os << "}"; return os;}
template <typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U> &p){os << '{' << p.first << ',' << p.second << '}'; return os;}

#define mp make_pair
#define pb push_back
#define pf push_front
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const int NINF = -0x3f3f3f40;
const ll INF_L = 0x3f3f3f3f3f3f3f3f;
const ll NINF_L = -0x3f3f3f3f3f3f3f40;
const int MAXN = 3e6+5;

struct node {
	int val;
	node() {
		val = 0;
		F0R(i, 26) ch[i] = nullptr;
		F0R(i, 26) end = false;
	}
	bool end;
	node* ch[26];
};

bool cmp(string& s1, string& s2) {
	return s1.size() < s2.size();
}

string arr[MAXN];
int ans = 0;

void dfs(node* curr) {
	pi gre{0, 0};
	int cSum = 0;
	F0R(i, 26) {
		if (curr->ch[i]) {
			dfs(curr->ch[i]);
			cSum += curr->ch[i]->end;
		}
	}
	F0R(i, 26) {
		if(curr->ch[i] && curr->ch[i]->end) {
			MAX(curr->val, curr->ch[i]->val+cSum);
			if(curr->ch[i]->val>gre.s) {
				gre.s = curr->ch[i]->val;
				if(gre.s>gre.f) swap(gre.s,gre.f);
			}
		}
	}
	MAX(ans, gre.f+gre.s+cSum+curr->end);
}

int main() {
	FAST_IO;
	int n; cin >> n;
	F0R(i, n) cin >> arr[i];
	sort(arr, arr + n, cmp);
	node* init = new node();
	F0R(i, n) {
		node* curr = init;
		F0Rd(j, arr[i].size() - 1) {
			if(!(curr->ch[arr[i][j] - 'a']))
				curr->ch[arr[i][j] - 'a'] = new node();
			curr = curr->ch[arr[i][j]-'a'];
		}
		curr->end = true;
	}
	dfs(init);
//	cout << '\n' << init->ch['a'-'a'] -> end << '\n';
	cout << ans << '\n';
}

//Remember to change MAXN if relevant!!!

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	94328 KB	Output is correct
2	Correct	75 ms	94388 KB	Output is correct
3	Correct	73 ms	94328 KB	Output is correct
4	Correct	464 ms	228752 KB	Output is correct
5	Correct	109 ms	98040 KB	Output is correct
6	Correct	169 ms	175372 KB	Output is correct
7	Correct	165 ms	175132 KB	Output is correct
8	Correct	178 ms	174936 KB	Output is correct
9	Correct	189 ms	180944 KB	Output is correct
10	Correct	162 ms	174944 KB	Output is correct