#include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef long long LL; typedef pair<LL,LL> PI; typedef vector<int> VI; #define MP make_pair #define PB push_back #define SD second #define FT first int k,n,m,q,d; const int N = 5003; const int M = 1003; const LL INF = 2000000000000000000LL; vector<int> rozbicie[N]; int s[N]; vector<int> akt; bool zawiera(vector<int>& dane, int k) { for(int i=0;i<(int)dane.size()-m;i++) { int ok = 1; for(int i2=0;i2<m;i2++) { if(dane[i+i2] != s[i2]){ok = 0;break;} } if(ok) return true; } return false; } void doklej(vector<int>& a, vector<int>& b) { for(int i=0;i<b.size();i++) a.PB(b[i]); } void rosnij(vector<int>& dane) { vector<int> kopia=dane; dane = vector<int>(); for(int i=0;i<kopia.size();i++) { doklej(dane, rozbicie[kopia[i]]); } } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { int l; scanf("%d",&l); for(int i2=0;i2<l;i2++) { int a; scanf("%d",&a);a--; rozbicie[i].PB(a); } } for (int i = 0; i < m; i++) { scanf("%d", &s[i]); s[i]--; } int res = -1; akt.PB(0); for(int i=1;i<20;i++) { if (akt.size() > 100000) break; if(zawiera(akt,i)){ res = i; break;} rosnij(akt); } printf("%d\n", res); }
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 | #include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef long long LL; typedef pair<LL,LL> PI; typedef vector<int> VI; #define MP make_pair #define PB push_back #define SD second #define FT first int k,n,m,q,d; const int N = 5003; const int M = 1003; const LL INF = 2000000000000000000LL; vector<int> rozbicie[N]; int s[N]; vector<int> akt; bool zawiera(vector<int>& dane, int k) { for(int i=0;i<(int)dane.size()-m;i++) { int ok = 1; for(int i2=0;i2<m;i2++) { if(dane[i+i2] != s[i2]){ok = 0;break;} } if(ok) return true; } return false; } void doklej(vector<int>& a, vector<int>& b) { for(int i=0;i<b.size();i++) a.PB(b[i]); } void rosnij(vector<int>& dane) { vector<int> kopia=dane; dane = vector<int>(); for(int i=0;i<kopia.size();i++) { doklej(dane, rozbicie[kopia[i]]); } } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { int l; scanf("%d",&l); for(int i2=0;i2<l;i2++) { int a; scanf("%d",&a);a--; rozbicie[i].PB(a); } } for (int i = 0; i < m; i++) { scanf("%d", &s[i]); s[i]--; } int res = -1; akt.PB(0); for(int i=1;i<20;i++) { if (akt.size() > 100000) break; if(zawiera(akt,i)){ res = i; break;} rosnij(akt); } printf("%d\n", res); } |