QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#360225 | #5034. >.< | Strywr | 70 | 180ms | 169264kb | C++20 | 5.9kb | 2024-03-21 15:32:55 | 2024-03-21 15:32:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ '0');
ch = getchar();
}
return x * f;
}
const int N = 1e6 + 10; const ll inf = 1e18;
int n, m, k; int fail[N], tot; vector<pair<int, int> > e[N];
unordered_map<int, int> trie[N]; vector<int> son[N]; int a[N];
int ed[N], nd[N]; vector<int> ef[N];
void insert(int len) {
int x = 0;
for (int i = 1; i <= len; i++) {
if (!trie[x][a[i]]) trie[x][a[i]] = ++tot, son[x].push_back(a[i]);
x = trie[x][a[i]]; nd[x] = a[i];
} ed[x] = 1;
}
void getfail() {
queue<int> q;
for (int i = 1; i <= n; i++) q.push(i);
while (q.size()) {
int u = q.front(); q.pop();
for (auto i : son[u]) {
int x = trie[u][i]; int nw = fail[u];
while (!trie[nw].count(i) && nw) nw = fail[nw];
fail[x] = trie[nw][i]; q.push(x); //!!!!!!!!!只要访问了就一定会建立出来,.count也是1了
}
}
}
int sz[N], id[N], num, ch[N]; bool vis[N];
void gethf(int u) {
if (ch[id[u]]) return; //自己不合法,整个子树也不合法了 ,
// 我们称每个路径的最后一个元素所在的点为不合法点,所有不合法点fail子树的点一定也不合法(因为能通过跳fail标记到不合法点)
//而且这些所有不合法点在trie树上的子树的点也一定不合法,因为子树里的点完全包含祖先的字符串,
//所以如果到达了子树,说明一定包含祖先的字符串,一定不可以
vis[u] = 1;
for (auto i : son[u]) {
int v = trie[u][i]; gethf(v);
}
}
void dfs(int u) {
sz[u] = 1; id[u] = ++num;
for (auto v : ef[u]) dfs(v), sz[u] += sz[v];
}
struct Seg {
int lc, rc, sum, v, w; //1~tot
}tr[N*20]; int cur, rt[N];//一共2e5个点 ,4e5次单点插入(1~n节点插入的原边 + n+1~tot节点插入的trie树上的边) 一共4e5
void pushup(int nw) {
tr[nw].sum = tr[tr[nw].lc].sum + tr[tr[nw].rc].sum;
}
void insert(int &p, int q, int l, int r, int x, int v, int w) {
p = ++cur; tr[p] = tr[q];
if (l == r) {
tr[p].sum = 1; tr[p].w = w; tr[p].v = v; return;
} int mid = (l + r) >> 1;
if (x <= mid) insert(tr[p].lc, tr[q].lc, l, mid, x, v, w);
else insert(tr[p].rc, tr[q].rc, mid + 1, r, x, v, w);
pushup(p);
}
void addedge() {
queue<int> q; q.push(0);
while (q.size()) {
int u = q.front(); q.pop();
for (auto i : son[u]) {
int x = trie[u][i]; if (!vis[x]) continue;
rt[x] = rt[fail[x]];
//!!!!!!!!!!!!!!!!!!!!!!!!可持久化线段树的下标不能是1~tot,这些AC自动机上的点
//而应该是1~n, 表示原图中的点。因为比如下面的样例,fail[5]=2,5从fail[5]里面继承了一个2->3的边
//继承过了也就是5链接到3,但是我们发现6对应的也是3,所以5实际上应该连接到6,如果我们直接加边,那么5->3
//的边就删除不了,而如果我们用1~n, 那么5->3 和 5->6的边都存在于下标2,可以直接覆盖
//每个叶子维护一个v,w 表示这个终点在AC自动机上对应的点,以及边权
// for (auto nw : e[nd[x]]) { //!!!!!!!!!!!!nw.first是原图的点,不是AC自动机的,而我们的连边是AC自动机的
// if (!trie[x].count(nw.first) && x > n) continue; //x <= n的那几个点在这个时候也要连边
// int to = trie[x].count(nw.first) ? trie[x][nw.first] : nw.first;
// if (vis[to]) insert(rt[x], rt[x], 1, tot, to, nw.second);
// } q.push(x);
//!!!!!!!!!!!!!!!应该是nd[x],因为nd[x]是原图的点,x是AC自动机上面的
for (auto nw : e[nd[x]]) { //!!!!!!!!!!!!nw.first是原图的点,不是AC自动机的,而我们的连边是AC自动机的
if (!trie[x].count(nw.first) && x > n) continue; //x <= n的那几个点在这个时候也要连边
int to = trie[x].count(nw.first) ? trie[x][nw.first] : nw.first;
insert(rt[x], rt[x], 1, n, nw.first, to, nw.second);
//!!!这里不能加vis[to],因为我们链接向这里,是为了删除原来的边,dij的时候判断掉!vis的点即可
} q.push(x);
}
}
}
ll dis[N]; bool viss[N];
struct qnode {
int u; ll d;
qnode(int uu, ll dd) {
u = uu; d = dd;
}
friend bool operator < (qnode a, qnode b) {
return a.d > b.d;
}
}; priority_queue<qnode> q;
void update(int nw, int l, int r, ll d) {
if (l == r) {
int x = tr[nw].v;
if (vis[x] && dis[x] > d + tr[nw].w) {
dis[x] = d + tr[nw].w; q.push(qnode(x, dis[x]));
} tr[nw].sum = 0; return;
} int mid = (l + r) >> 1;
if (tr[tr[nw].lc].sum) update(tr[nw].lc, l, mid, d);
if (tr[tr[nw].rc].sum) update(tr[nw].rc, mid + 1, r, d);
pushup(nw);
}
void dij() {
if (!vis[1]) {cout << -1; exit(0);}
for (int i = 1; i <= tot; i++) dis[i] = inf;
dis[1] = 0; q.push(qnode(1, 0));
while (q.size()) {
int u = q.top().u; q.pop();
if (viss[u]) continue;
viss[u] = 1; update(rt[u], 1, n, dis[u]);
} ll ans = inf;
for (int i = 1; i <= tot; i++) {
if (nd[i] == n && vis[i]) {
ans = min(ans, dis[i]);
}
}
if (ans == inf) ans = -1;
cout << ans;
}
//!!!!!!!!!!!!!!!!!!!!++cur
int main() {
n = read(), m = read(), k = read();
for (int i = 1; i <= n; i++) trie[0][i] = ++tot, son[0].push_back(i), nd[tot] = i;
for (int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
e[u].push_back(make_pair(v, w));
}
for (int i = 1; i <= k; i++) {
int p = read();
for (int j = 1; j <= p; j++) a[j] = read();
insert(p);
} getfail(); for (int i = 1; i <= tot; i++) ef[fail[i]].push_back(i); dfs(0);
for (int i = 1; i <= tot; i++) { //1~n是自己加入的单点
if (ed[i]) ch[id[i]]++, ch[id[i]+sz[i]]--; //子树标记
} for (int i = 1; i <= num; i++) ch[i] += ch[i-1];
gethf(0); addedge(); dij();
return 0;
}
/*
4 4 1
1 2 1
2 3 1
3 4 1
3 2 1
4 1 2 3 4
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 15ms
memory: 61024kb
input:
35 100 0 34 7 447733879 24 20 187005344 14 34 654502303 2 31 865194349 20 33 9517055 33 15 991889891 24 33 395599993 13 16 237525328 9 5 373850826 30 34 391470240 10 7 650077565 26 10 400825980 34 27 189924713 19 27 907609573 20 10 614945312 10 5 960007605 1 7 984076202 32 25 539699728 24 31 2553027...
output:
1970522617
result:
ok single line: '1970522617'
Test #2:
score: 0
Accepted
time: 20ms
memory: 63092kb
input:
35 100 0 3 12 720466531 8 12 396056603 29 21 717362482 34 13 785882968 7 13 748993858 9 28 371041056 5 22 279747660 10 13 511029466 9 10 90421686 24 13 68485905 12 17 589986641 26 3 49095373 15 24 515201376 10 33 672973479 29 31 705185599 27 22 689337965 20 4 145960570 31 28 136121037 28 5 202143094...
output:
2296067497
result:
ok single line: '2296067497'
Test #3:
score: 0
Accepted
time: 20ms
memory: 65148kb
input:
35 100 0 22 20 355360466 23 35 601550723 3 27 186544474 6 24 134507727 25 2 672165808 19 1 711018563 32 16 669385420 27 11 750652665 14 11 158441860 25 14 53347528 2 20 140122295 33 20 112964489 14 6 253781013 18 14 771123144 17 35 508607402 3 19 403442205 30 16 336645858 24 22 470183063 31 22 10734...
output:
1517028140
result:
ok single line: '1517028140'
Test #4:
score: 0
Accepted
time: 10ms
memory: 63032kb
input:
35 100 0 32 5 808438527 26 23 888346324 14 19 992303007 23 1 278329540 17 29 587913784 4 33 770924125 2 5 605204525 1 21 657667587 9 35 444108546 22 12 391857443 31 33 184589665 7 14 826884170 10 32 241928783 3 17 634515992 9 34 429624654 1 18 736971857 6 9 625772037 20 18 344038507 12 25 24408330 4...
output:
1502429426
result:
ok single line: '1502429426'
Test #5:
score: 0
Accepted
time: 13ms
memory: 62988kb
input:
35 100 0 1 9 150223804 13 25 225623874 27 10 826064515 7 31 111586392 27 4 627187519 8 7 517189480 10 13 427167940 24 14 563496 27 23 119441879 13 31 712972744 34 13 128158051 16 13 146964967 31 14 860155206 25 5 431208773 24 11 48709486 29 10 694088474 11 1 801122521 12 10 369399315 21 29 399505482...
output:
1355451140
result:
ok single line: '1355451140'
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 20
Accepted
time: 14ms
memory: 60332kb
input:
35 100 10 11 2 380526516 9 1 213280408 20 1 775174358 23 33 14349082 32 11 781584201 10 26 572662203 8 12 157664649 23 20 327195474 15 25 861545590 6 18 838910534 21 27 91640650 19 26 995166014 4 2 878565098 4 34 523383573 26 18 578962566 31 6 874478934 11 8 398592349 10 7 643306798 13 28 290421417 ...
output:
1980354133
result:
ok single line: '1980354133'
Test #7:
score: 0
Accepted
time: 16ms
memory: 59612kb
input:
35 100 10 11 1 896687117 7 26 476711390 5 32 630956 6 4 823883738 21 34 247010132 3 12 913937169 16 12 430385321 16 5 852671069 26 21 985342803 30 6 434242228 29 8 425264910 4 20 270204170 30 29 682115837 17 15 583261079 26 28 747023051 34 5 467933832 8 35 286976257 18 28 122472413 17 2 139111605 31...
output:
1221466953
result:
ok single line: '1221466953'
Test #8:
score: 0
Accepted
time: 16ms
memory: 58456kb
input:
35 100 10 22 1 14962104 21 6 543325859 8 34 566018166 33 20 98618235 25 17 262818303 12 20 406329400 8 18 609453514 24 2 538644514 9 19 692253675 2 35 402502466 6 22 643342764 32 22 125016732 24 15 592478175 9 4 983207384 27 1 8572978 33 11 455386297 8 6 80900833 21 18 876759575 6 3 498241363 3 27 7...
output:
2366165329
result:
ok single line: '2366165329'
Test #9:
score: 0
Accepted
time: 16ms
memory: 59900kb
input:
35 100 10 9 11 824356486 26 28 495355000 18 7 722666675 13 28 916320626 23 5 902191290 24 15 565350882 7 25 395415147 1 15 174378000 32 27 314954867 32 4 620502039 14 8 369888464 30 10 174528922 19 8 225961839 3 18 287338530 32 6 194825575 4 7 434071787 26 22 760578181 2 14 778364759 15 21 672777506...
output:
4621773448
result:
ok single line: '4621773448'
Test #10:
score: 0
Accepted
time: 10ms
memory: 59480kb
input:
35 100 10 8 1 955842345 8 26 487841115 13 11 431659053 32 35 736554102 34 8 223723748 2 6 474854267 10 13 343831244 9 31 652218719 33 21 18870804 21 3 657281305 33 30 354153202 13 29 96716199 13 7 930885678 28 2 403915674 12 7 428085923 9 28 518591614 27 33 676639919 7 16 293763983 29 21 317079692 8...
output:
-1
result:
ok single line: '-1'
Subtask #3:
score: 30
Accepted
Test #11:
score: 30
Accepted
time: 173ms
memory: 140116kb
input:
50000 200000 1 7542 37166 116613326 3581 43961 629220971 12873 42953 440313807 31744 5286 697832848 25882 12748 106667302 34760 29676 181570340 41570 9240 885513989 22227 35688 63657981 43180 29194 174058940 8977 41899 48262624 7465 18291 600002514 46925 9281 951474878 2115 31162 373758881 5386 3798...
output:
2526392504
result:
ok single line: '2526392504'
Test #12:
score: 0
Accepted
time: 140ms
memory: 145600kb
input:
50000 200000 1 24782 12463 176168576 48875 16935 741763277 36966 21304 496529510 23163 41091 139899126 22017 12255 642957842 20239 21407 267962408 9992 39550 648664588 46678 18079 745576109 21525 40647 668173200 15499 45167 948835398 236 25231 504169193 1144 26236 160922096 5068 22529 596773743 2293...
output:
2916905009
result:
ok single line: '2916905009'
Test #13:
score: 0
Accepted
time: 143ms
memory: 142472kb
input:
50000 200000 1 44987 47473 603921908 19076 14543 979792861 40477 5097 975772708 10156 43592 986014532 38276 14331 883008937 27568 17017 379894398 20669 13688 619117263 10452 28268 302961670 49932 14669 219573245 21299 37089 111817304 166 9139 579564241 39624 47105 454768157 36321 44135 475008487 154...
output:
2437330315
result:
ok single line: '2437330315'
Test #14:
score: 0
Accepted
time: 170ms
memory: 143624kb
input:
50000 200000 1 23044 25813 938979371 13825 12053 600535744 40300 48533 976220497 27950 9733 185539918 17753 40163 441723428 16971 12159 195868379 46052 16991 663733811 7358 22733 618903475 2686 14738 147547542 35603 33025 563640588 27600 13132 146407801 4349 35144 646562628 34069 5239 661848564 2670...
output:
2525861695
result:
ok single line: '2525861695'
Test #15:
score: 0
Accepted
time: 143ms
memory: 145920kb
input:
50000 200000 1 7010 49706 41082166 103 46014 91170674 28554 6661 235249419 24817 37664 390481853 21256 38170 713774964 5638 33537 671772217 18117 23810 806403210 4928 24506 263165151 19583 15308 101634127 1571 48099 527342772 46438 27069 966211201 12628 13976 545976032 48175 1310 804025336 22339 471...
output:
2343184542
result:
ok single line: '2343184542'
Subtask #4:
score: 0
Time Limit Exceeded
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #16:
score: 30
Accepted
time: 169ms
memory: 167180kb
input:
100000 200000 1000 19301 9982 475809376 52647 57952 928799166 9946 15118 40293182 66459 51732 326545014 80330 52390 715066088 31148 24539 119871789 57032 47286 947993583 98743 49894 241867216 60086 21505 368954791 91768 49801 542930073 60256 30453 412799483 36211 89359 653932077 45566 53313 15684003...
output:
8083327502
result:
ok single line: '8083327502'
Test #17:
score: 0
Accepted
time: 173ms
memory: 167152kb
input:
100000 200000 1000 80075 68116 142970144 36601 15061 355242020 92568 95586 525501865 88685 38697 187866032 14520 30560 541191778 56724 37390 515750178 18884 72571 242089567 41181 98841 550088819 65162 48127 817224281 74290 68998 694769252 14496 15293 240590474 93890 16543 306889224 76237 85271 38310...
output:
6805440468
result:
ok single line: '6805440468'
Test #18:
score: 0
Accepted
time: 158ms
memory: 169264kb
input:
100000 200000 1000 54902 45565 209744243 7916 74828 542255326 74913 75406 694953563 60977 27774 696350584 4357 78374 695819954 73651 93310 927896743 78422 69874 765148628 4340 11648 831353168 73481 54277 159880801 30642 18345 948964021 12981 62022 492589556 42037 69233 157973044 64535 41068 51105435...
output:
6889144412
result:
ok single line: '6889144412'
Test #19:
score: 0
Accepted
time: 180ms
memory: 165760kb
input:
100000 200000 1000 75982 60451 883166605 68067 20900 877134639 51374 19523 268232604 29382 99013 305216607 1991 26063 982636024 53030 72285 849876664 86016 44259 426860064 74173 17758 236299680 31639 57016 119442138 59029 31790 496971527 41939 33688 647056718 91622 87349 884517745 31301 53781 125813...
output:
4650222261
result:
ok single line: '4650222261'
Test #20:
score: -30
Time Limit Exceeded
input:
100000 199996 49998 1 2 1 2 50000 1 1 3 1 3 50000 1 1 4 1 4 50000 1 1 5 1 5 50000 1 1 6 1 6 50000 1 1 7 1 7 50000 1 1 8 1 8 50000 1 1 9 1 9 50000 1 1 10 1 10 50000 1 1 11 1 11 50000 1 1 12 1 12 50000 1 1 13 1 13 50000 1 1 14 1 14 50000 1 1 15 1 15 50000 1 1 16 1 16 50000 1 1 17 1 17 50000 1 1 18 1 1...