#include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <map> using namespace std; typedef long long int LL; struct wp { int t[1003]; int l; LL hasz[1003]; }t[1003]; struct ciag { vector <int> v; int wyn; }; LL pot[1003], hsz[1003]; int wz[1003]; const LL lp=503; const LL mod=(LL)1e9+696969; int P[2015]; queue <ciag> q, pq; vector <int> v; LL rhsz (int a, int b) { LL odp=(hsz[b]-(hsz[a-1]*pot[b-a+1])%mod)%mod; if (odp<0) odp+=mod; return odp; } LL rthasz (int a, int b, int i) { LL odp=(t[i].hasz[b]-(t[i].hasz[a-1]*pot[b-a+1])%mod)%mod; if (odp<0) odp+=mod; return odp; } void view () { for (vector<int>::iterator it=v.begin(); it!=v.end(); it++) printf ("%d ", *it); printf ("\n"); } map<LL, int> mp; int main () { int n, m, x, y, dl, wyn, po, ko, sr, szuk, dozuc, dlg; pot[0]=1; for (int i=1; i<=1001; i++) pot[i]=(pot[i-1]*lp)%mod; scanf ("%d%d", &n, &m); for (int i=1; i<=n; i++) { scanf ("%d", &t[i].l); for (int j=1; j<=t[i].l; j++) { scanf ("%d", &t[i].t[j]); t[i].hasz[j]=(t[i].hasz[j-1]*lp+t[i].t[j])%mod; } } /*for (int i=1; i<=n; i++) { printf ("%d : ", i); for (int j=1; j<=t[i].l; j++) printf ("%lld ", t[i].hasz[j]); printf ("\n"); }*/ for (int i=1; i<=m; i++) { scanf ("%d", &x); v.push_back(x); } ciag pom; pom.v=v; pom.wyn=1; q.push(pom); v.clear(); int dzies=10; while (!q.empty()) { wyn=q.front().wyn; dl=q.front().v.size(); v=q.front().v; for (int i=0; i<dl; i++) wz[i+1]=v[i]; //printf ("wynik : {%d} ", wyn); for (int i=1; i<=dl; i++) { hsz[i]=(hsz[i-1]*lp+wz[i])%mod; //printf ("%d ", wz[i]); } /*printf ("\n"); for (int i=1; i<=dl; i++) printf ("%lld ", hsz[i]);*/ if (dl==1 && q.front().v[0]==1) { printf ("%d", wyn); return 0; } q.pop(); if (mp[hsz[dl]]==1) { //printf ("blad\n"); continue; } //printf ("\n"); mp[hsz[dl]]=1; for (int i=1; i<=n; i++) { for (int j=dl; j<=t[i].l; j++) if (rthasz(j-dl+1, j, i)==hsz[dl]) { v.clear(); v.push_back(i); pom.v=v; pom.wyn=wyn+1; q.push(pom); } } //printf ("%lld", hsz[dl]); for (int i=1; i<=n; i++) { po=0; ko=min(t[i].l, dl); sr=ko; while (sr>0) { //sr=(po+ko)/2+1; //printf ("%d %d %d %d %d %d %lld %lld\n", i, sr, 1, sr, t[i].l-sr+1, t[i].l, rhsz(1, sr), rthasz(t[i].l-sr+1, t[i].l, i)); if (rhsz(1, sr)==rthasz(t[i].l-sr+1, t[i].l, i)) break; sr--; } po=sr; //printf ("pocz : %d %d\n", i, po); if (po==0) continue; v.clear(); v.push_back(i); pom.v=v; pom.wyn=po+1; pq.push(pom); //printf ("zaczynamy : {%d} ", po+1); view(); while (!pq.empty()) { szuk=pq.front().wyn; v=pq.front().v; //printf ("w srodku : "); view(); pq.pop(); if (szuk>dl) continue; for (int j=1; j<=n; j++) { dlg=min(dl-szuk+1, t[j].l); //printf ("%d %d %d %d %d %lld %lld\n", j, szuk, szuk+dlg-1, 1, dlg, rhsz(szuk, szuk+dlg-1), rthasz(1, dlg, j)); if (rhsz(szuk, szuk+dlg-1)==rthasz(1, dlg, j)) { v.push_back(j); dozuc=szuk+dlg; pom.v=v; //printf ("pushuje : "); view(); if (dozuc>dl) { pom.wyn=wyn+1; q.push(pom); //printf ("q\n"); } else { pom.wyn=dozuc; pq.push(pom); //printf ("pq\n"); } v.pop_back(); } } } } } printf ("-1"); return 0; }
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 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 | #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <map> using namespace std; typedef long long int LL; struct wp { int t[1003]; int l; LL hasz[1003]; }t[1003]; struct ciag { vector <int> v; int wyn; }; LL pot[1003], hsz[1003]; int wz[1003]; const LL lp=503; const LL mod=(LL)1e9+696969; int P[2015]; queue <ciag> q, pq; vector <int> v; LL rhsz (int a, int b) { LL odp=(hsz[b]-(hsz[a-1]*pot[b-a+1])%mod)%mod; if (odp<0) odp+=mod; return odp; } LL rthasz (int a, int b, int i) { LL odp=(t[i].hasz[b]-(t[i].hasz[a-1]*pot[b-a+1])%mod)%mod; if (odp<0) odp+=mod; return odp; } void view () { for (vector<int>::iterator it=v.begin(); it!=v.end(); it++) printf ("%d ", *it); printf ("\n"); } map<LL, int> mp; int main () { int n, m, x, y, dl, wyn, po, ko, sr, szuk, dozuc, dlg; pot[0]=1; for (int i=1; i<=1001; i++) pot[i]=(pot[i-1]*lp)%mod; scanf ("%d%d", &n, &m); for (int i=1; i<=n; i++) { scanf ("%d", &t[i].l); for (int j=1; j<=t[i].l; j++) { scanf ("%d", &t[i].t[j]); t[i].hasz[j]=(t[i].hasz[j-1]*lp+t[i].t[j])%mod; } } /*for (int i=1; i<=n; i++) { printf ("%d : ", i); for (int j=1; j<=t[i].l; j++) printf ("%lld ", t[i].hasz[j]); printf ("\n"); }*/ for (int i=1; i<=m; i++) { scanf ("%d", &x); v.push_back(x); } ciag pom; pom.v=v; pom.wyn=1; q.push(pom); v.clear(); int dzies=10; while (!q.empty()) { wyn=q.front().wyn; dl=q.front().v.size(); v=q.front().v; for (int i=0; i<dl; i++) wz[i+1]=v[i]; //printf ("wynik : {%d} ", wyn); for (int i=1; i<=dl; i++) { hsz[i]=(hsz[i-1]*lp+wz[i])%mod; //printf ("%d ", wz[i]); } /*printf ("\n"); for (int i=1; i<=dl; i++) printf ("%lld ", hsz[i]);*/ if (dl==1 && q.front().v[0]==1) { printf ("%d", wyn); return 0; } q.pop(); if (mp[hsz[dl]]==1) { //printf ("blad\n"); continue; } //printf ("\n"); mp[hsz[dl]]=1; for (int i=1; i<=n; i++) { for (int j=dl; j<=t[i].l; j++) if (rthasz(j-dl+1, j, i)==hsz[dl]) { v.clear(); v.push_back(i); pom.v=v; pom.wyn=wyn+1; q.push(pom); } } //printf ("%lld", hsz[dl]); for (int i=1; i<=n; i++) { po=0; ko=min(t[i].l, dl); sr=ko; while (sr>0) { //sr=(po+ko)/2+1; //printf ("%d %d %d %d %d %d %lld %lld\n", i, sr, 1, sr, t[i].l-sr+1, t[i].l, rhsz(1, sr), rthasz(t[i].l-sr+1, t[i].l, i)); if (rhsz(1, sr)==rthasz(t[i].l-sr+1, t[i].l, i)) break; sr--; } po=sr; //printf ("pocz : %d %d\n", i, po); if (po==0) continue; v.clear(); v.push_back(i); pom.v=v; pom.wyn=po+1; pq.push(pom); //printf ("zaczynamy : {%d} ", po+1); view(); while (!pq.empty()) { szuk=pq.front().wyn; v=pq.front().v; //printf ("w srodku : "); view(); pq.pop(); if (szuk>dl) continue; for (int j=1; j<=n; j++) { dlg=min(dl-szuk+1, t[j].l); //printf ("%d %d %d %d %d %lld %lld\n", j, szuk, szuk+dlg-1, 1, dlg, rhsz(szuk, szuk+dlg-1), rthasz(1, dlg, j)); if (rhsz(szuk, szuk+dlg-1)==rthasz(1, dlg, j)) { v.push_back(j); dozuc=szuk+dlg; pom.v=v; //printf ("pushuje : "); view(); if (dozuc>dl) { pom.wyn=wyn+1; q.push(pom); //printf ("q\n"); } else { pom.wyn=dozuc; pq.push(pom); //printf ("pq\n"); } v.pop_back(); } } } } } printf ("-1"); return 0; } |