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
|