library
This documentation is automatically generated by online-judge-tools/verification-helper
test/aoj0438.test.cpp
- View this file on GitHub
- Last update: 2021-06-21 15:51:55+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0438
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0438"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;
template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
#include "../string/rolling_hash_ull.cpp"
#include "../util/makev.cpp"
int main() {
int n, m;
cin >> n >> m;
vector<char> c(n);
for (auto &&i : c) cin >> i;
vector<vector<int>> G(n);
for (int i = 0; i < m; ++i) {
int a, b;
scanf("%d %d", &a, &b);
a--; b--;
G[a].emplace_back(b);
}
rolling_hash_ull ro(n);
int B = 19;
auto dp = make_v(B, n, ull(0));
auto to = make_v(B, n, -1);
for (int i = 0; i+1 < n; ++i) {
G[i].emplace_back(i+1);
}
auto ok = [&](int x, int y){
for (int i = B-1; i >= 0; --i) {
if(~to[i][x] && ~to[i][y] && dp[i][x] == dp[i][y]){
x = to[i][x], y = to[i][y];
}
}
while(true){
if(c[x] != c[y]) return c[x] < c[y];
x = to[0][x], y = to[0][y];
if(y == -1) return false;
if(x == -1) return true;
}
};
for (int i = n-1; i >= 0; --i) {
for (auto &&j : G[i]) {
if(to[0][i] == -1 || ok(j, to[0][i])) to[0][i] = j;
}
if(to[0][i] != -1){
dp[0][i] = c[i];
for (int j = 1; j < B; ++j) {
to[j][i] = to[j-1][to[j-1][i]];
if(~to[j][i]) {
dp[j][i] = ro.mul(dp[j-1][i], ro.p()[1 << (j-1)])+dp[j-1][to[j-1][i]];
if(dp[j][i] >= M) dp[j][i] -= M;
}else break;
}
}
}
int x = 0;
while(true){
cout << c[x];
if(x == n-1) break;
x = to[0][x];
}
puts("");
return 0;
}#line 1 "test/aoj0438.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0438"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;
template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
#line 1 "string/rolling_hash_ull.cpp"
#include <chrono>
constexpr ull M = (1UL << 61) - 1;
constexpr ull POSITIVISER = M * 3;
constexpr ull MASK30 = (1UL << 30) - 1;
constexpr ull MASK31 = (1UL << 31) - 1;
class rolling_hash_ull {
static ull get_base(){
ull z = (static_cast<uint64_t>((chrono::system_clock::now().time_since_epoch().count())&((1LL << 32)-1)))+0x9e3779b97f4a7c15;
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
return z;
}
static inline ull calc_mod(ull val){
val = (val & M) + (val >> 61);
if(val > M) val -= M;
return val;
}
public:
vector<ull> hash;
static ull &B() {
static ull B_ = (get_base())%(M-2)+2;
return B_;
}
static vector<ull> &p() {
static vector<ull> p_{1, B()};
return p_;
}
static inline ull mul(ull x, ull y){
ull a = x >> 31, b = x & MASK31, c = y >> 31, d = y & MASK31, e = b*c+a*d;
return (a*c << 1) + b*d + ((e & MASK30) << 31) + (e >> 30);
}
rolling_hash_ull(const string &s) {
if(p().size() <= s.size()){
int l = p().size();
p().resize(s.size()+1);
for (int i = l; i < p().size(); ++i) {
p()[i] = calc_mod(mul(p()[i-1], p()[1]));
}
}
hash.resize(s.size()+1, 0);
for (int i = 0; i < s.size(); ++i) {
hash[i+1] = calc_mod(mul(hash[i],B()) + s[i]);
}
};
rolling_hash_ull(const int& n){
int l = p().size();
p().resize(n+1);
for (int i = l; i < p().size(); ++i) {
p()[i] = calc_mod(mul(p()[i-1], p()[1]));
}
}
ull get(int l, int r){
return calc_mod(hash[r] + POSITIVISER - mul(hash[l], p()[r-l]));
}
static ull val(string &s){
if(p().size() <= s.size()){
int l = p().size();
p().resize(s.size()+1);
for (int i = l; i < p().size(); ++i) {
p()[i] = calc_mod(mul(p()[i-1], p()[1]));
}
}
ull ret = 0;
for (int i = 0; i < s.size(); ++i) {
ret = calc_mod(mul(ret, B()) + s[i]);
}
return ret;
}
};
#line 1 "util/makev.cpp"
template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }
template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }
template<class T> void chmin(T &a, const T &b){ a = (a < b ? a : b); }
template<class T> void chmax(T &a, const T &b){ a = (a > b ? a : b); }
/**
* @brief make_v, chmin, chmax
* @docs _md/makev.md
*/
#line 22 "test/aoj0438.test.cpp"
int main() {
int n, m;
cin >> n >> m;
vector<char> c(n);
for (auto &&i : c) cin >> i;
vector<vector<int>> G(n);
for (int i = 0; i < m; ++i) {
int a, b;
scanf("%d %d", &a, &b);
a--; b--;
G[a].emplace_back(b);
}
rolling_hash_ull ro(n);
int B = 19;
auto dp = make_v(B, n, ull(0));
auto to = make_v(B, n, -1);
for (int i = 0; i+1 < n; ++i) {
G[i].emplace_back(i+1);
}
auto ok = [&](int x, int y){
for (int i = B-1; i >= 0; --i) {
if(~to[i][x] && ~to[i][y] && dp[i][x] == dp[i][y]){
x = to[i][x], y = to[i][y];
}
}
while(true){
if(c[x] != c[y]) return c[x] < c[y];
x = to[0][x], y = to[0][y];
if(y == -1) return false;
if(x == -1) return true;
}
};
for (int i = n-1; i >= 0; --i) {
for (auto &&j : G[i]) {
if(to[0][i] == -1 || ok(j, to[0][i])) to[0][i] = j;
}
if(to[0][i] != -1){
dp[0][i] = c[i];
for (int j = 1; j < B; ++j) {
to[j][i] = to[j-1][to[j-1][i]];
if(~to[j][i]) {
dp[j][i] = ro.mul(dp[j-1][i], ro.p()[1 << (j-1)])+dp[j-1][to[j-1][i]];
if(dp[j][i] >= M) dp[j][i] -= M;
}else break;
}
}
}
int x = 0;
while(true){
cout << c[x];
if(x == n-1) break;
x = to[0][x];
}
puts("");
return 0;
}