Submission #64735

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>
using namespace std;
struct RollingHash {
static const uint64_t mod = (1ull << 61ull) - 1;
using uint128_t = __uint128_t;
vector< uint64_t > hashed, power;
const uint64_t base;
static inline uint64_t add(uint64_t a, uint64_t b) {
if((a += b) >= mod) a -= mod;
return a;
}
static inline uint64_t mul(uint64_t a, uint64_t b) {
uint128_t c = (uint128_t) a * b;
return add(c >> 61, c & mod);
}
static inline uint64_t generate_base() {
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution< uint64_t > rand(1, RollingHash::mod - 1);
return rand(mt);
}
RollingHash() = default;
RollingHash(const string &s, uint64_t base) : base(base) {
size_t sz = s.size();
hashed.assign(sz + 1, 0);
power.assign(sz + 1, 0);
power[0] = 1;
for(int i = 0; i < sz; i++) {
power[i + 1] = mul(power[i], base);
hashed[i + 1] = add(mul(hashed[i], base), s[i]);
}
}
template< typename T >
RollingHash(const vector< T > &s, uint64_t base) : base(base) {
size_t sz = s.size();
hashed.assign(sz + 1, 0);
power.assign(sz + 1, 0);
power[0] = 1;
for(int i = 0; i < sz; i++) {
power[i + 1] = mul(power[i], base);
hashed[i + 1] = add(mul(hashed[i], base), s[i]);
}
}
uint64_t query(int l, int r) const {
return add(hashed[r], mod - mul(hashed[l], power[r - l]));
}
uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) const {
return add(mul(h1, power[h2len]), h2);
}
int lcp(const RollingHash &b, int l1, int r1, int l2, int r2) const {
assert(base == b.base);
int len = min(r1 - l1, r2 - l2);
int low = 0, high = len + 1;
while(high - low > 1) {
int mid = (low + high) / 2;
if(query(l1, l1 + mid) == b.query(l2, l2 + mid)) low = mid;
else high = mid;
}
return low;
}
};
signed main(void){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<char> c(n);
vector<vector<int> > edge(n);
for(int i = 0; i < n; ++i){
cin >> c[i];
}
RollingHash rh(c, RollingHash::generate_base());
for(int i = 0; i < m; ++i){
int u, v;
cin >> u >> v;
--u, --v;
edge[u].emplace_back(v);
}
vector nxt(n, vector(21, -1));
vector hash(n, vector(21, 0ULL));
vector<int> dist(n);
auto comp = [&](int a, int b) -> int{
if(dist[a] > dist[b]) swap(a, b);
int copy_a = a, copy_b = b;
if(c[a] != c[b]){
if(c[a] < c[b]){
return (a);
}else{
return (b);
}
}
for(int i = 20; i >= 0; --i){
if(nxt[a][i] != -1 && hash[a][i] == hash[b][i]){
a = nxt[a][i];
b = nxt[b][i];
}
}
if(nxt[a][0] == -1){
return (copy_a);
}else if(c[nxt[a][0]] < c[nxt[b][0]]){
return (copy_a);
}else{
return (copy_b);
}
};
for(int i = n-2; i >= 0; --i){
int min_pos = i+1;
for(auto e : edge[i]){
min_pos = comp(min_pos, e);
}
nxt[i][0] = min_pos;
hash[i][0] = rh.query(min_pos, min_pos + 1);
dist[i] = dist[min_pos] + 1;
for(int j = 0; j < 20; ++j){
if(nxt[i][j] == -1){
nxt[i][j+1] = -1;
}else{
nxt[i][j+1] = nxt[nxt[i][j]][j];
hash[i][j+1] = rh.combine(hash[i][j], hash[nxt[i][j]][j], 1 << j);
}
}
}
string res;
int now = 0;
while(now != -1){
res.push_back(c[now]);
now = nxt[now][0];
}
cout << res << '\n';
return 0;
}

ステータス

項目 データ
問題 1447 - パスポート
ユーザー名 syoribu
投稿日時 2020-11-15 22:40:47
言語 C++17
状態 Accepted
得点 13
ソースコード長 3947 Byte
最大実行時間 595 ms
最大メモリ使用量 117252 KB

セット

セット 得点 Cases
1 ALL 13 / 13 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 23 ms 600 KB
1
in2 AC 20 ms 1220 KB
1
in3 AC 19 ms 2752 KB
1
in4 AC 16 ms 3036 KB
1
in5 AC 15 ms 3116 KB
1
in6 AC 30 ms 3068 KB
1
in7 AC 20 ms 3016 KB
1
in8 AC 24 ms 3084 KB
1
in9 AC 22 ms 3508 KB
1
in10 AC 28 ms 4392 KB
1
in11 AC 109 ms 38536 KB
1
in12 AC 114 ms 38576 KB
1
in13 AC 107 ms 38736 KB
1
in14 AC 280 ms 117252 KB
1
in15 AC 274 ms 112992 KB
1
in16 AC 249 ms 111488 KB
1
in17 AC 202 ms 113956 KB
1
in18 AC 180 ms 113852 KB
1
in19 AC 503 ms 96516 KB
1
in20 AC 595 ms 103860 KB
1
in21 AC 575 ms 91276 KB
1
in22 AC 231 ms 104240 KB
1
in23 AC 227 ms 103268 KB
1
in24 AC 176 ms 77032 KB
1
in25 AC 519 ms 109920 KB
1
in26 AC 496 ms 104936 KB
1
in27 AC 361 ms 93968 KB
1
in28 AC 439 ms 83196 KB
1
in29 AC 537 ms 95072 KB
1
in30 AC 566 ms 105000 KB
1
in31 AC 173 ms 81960 KB
1
in32 AC 187 ms 80228 KB
1
in33 AC 239 ms 109468 KB
1