結果

問題 No.515 典型LCP
コンテスト
ユーザー pekempey
提出日時 2017-05-05 22:54:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,549 bytes
コンパイル時間 1,152 ms
コンパイル使用メモリ 86,696 KB
実行使用メモリ 98,308 KB
最終ジャッジ日時 2024-09-14 08:56:31
合計ジャッジ時間 21,497 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

using namespace std;

vector<int> sufarray(const vector<int> &s) {
	const int n = s.size();
	vector<int> sa(n + 1);
	vector<int> r0(n + 1, -1);
	vector<int> r1(n + 1, -1);
	iota(sa.begin(), sa.end(), 0);
	for (int i = 0; i < n; i++) {
		r0[i] = s[i];
	}
	for (int k = 1; k <= n; k *= 2) {
		auto cmp = [&](int i, int j) {
			if (r0[i] != r0[j]) return r0[i] < r0[j];
			int ri = i + k <= n ? r0[i + k] : -1;
			int rj = j + k <= n ? r0[j + k] : -1;
			return ri < rj;
		};
		sort(sa.begin(), sa.end(), cmp);
		int r = 0;
		r1[sa[0]] = 0;
		for (int i = 0; i < n; i++) {
			r1[sa[i + 1]] = r1[sa[i]] + cmp(sa[i], sa[i + 1]);
		}
		swap(r0, r1);
	}
	return sa;
}

vector<int> lcparray(const vector<int> &s, const vector<int> &sa) {
	const int n = s.size();
	vector<int> isa(n + 1), lcp(n + 1);
	for (int i = 0; i <= n; i++) {
		isa[sa[i]] = i;
	}
	int k = 0;
	for (int i = 0; i < n; i++) {
		int j = sa[isa[i] - 1];
		k = max(0, k - 1);
		while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
		lcp[isa[i] - 1] = k;
	}
	return lcp;
}

struct RMQ {
	vector<int> lg;
	vector<vector<int>> dat;

	RMQ(const vector<int> &a) {
		const int n = a.size();
		lg.resize(n + 1);
		for (int i = 2; i <= n; i++) {
			lg[i] = lg[i / 2] + 1;
		}
		const int m = lg[n];
		dat.assign(m + 1, vector<int>(n));
		for (int i = 0; i < n; i++) {
			dat[0][i] = a[i];
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j + (1 << i) < n; j++) {
				dat[i + 1][j] = min(dat[i][j], dat[i][j + (1 << i)]);
			}
		}
	}

	int getmin(int l, int r) {
		int k = lg[r - l];
		return min(dat[k][l], dat[k][r - (1 << k)]);
	}
};

int main() {
	int n;
	cin >> n;

	vector<string> s(n);
	vector<int> start(n);
	vector<int> t;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		start[i] = t.size();
		for (char c : s[i]) {
			t.push_back(c);
		}
		t.push_back(i + 'z' + 1);
	}

	auto sa = sufarray(t);
	auto lcp = lcparray(t, sa);

	vector<int> isa(t.size() + 1);
	for (int i = 0; i <= t.size(); i++) {
		isa[sa[i]] = i;
	}

	RMQ rmq(lcp);

	int m, x, d;
	cin >> m >> x >> d;

	long long ans = 0;
	for (int k = 0; k < m; k++) {
		int i = (x / (n - 1)) + 1;
		int j = (x % (n - 1)) + 1;
		if (i > j) {
			swap(i, j);
		} else {
			j = j + 1;
		}
		x = (x + d) % (1LL * n * (n - 1));
		i--;
		j--;
		if (isa[start[i]] > isa[start[j]]) {
			swap(i, j);
		}
		if (i == j) {
			ans += s[i].size();
		} else {
			ans += rmq.getmin(isa[start[i]], isa[start[j]]);
		}
	}
	cout << ans << endl;
}
0