#include <cstdio> #include <algorithm> #include <vector> using namespace std; vector<vector<int> > keys; vector<int> endValue; vector<int> tmp; bool test(std::vector<int> & tmp2){ //check if tmp containts endValue //printf("tmp.size(): %d, end.size(): %d\n", tmp.size(), endValue.size()); if(tmp2.size() < endValue.size())return false; //printf("cool\n"); for(int i = 0; i < tmp2.size(); i++){ if(tmp2[i]==endValue[0]){ //printf("asd: %d\n", tmp[i]); bool areEqual=true; for(int j = 1; j < endValue.size(); j++){ if(i+j >= tmp2.size() || tmp2[i+j]!=endValue[j]){ areEqual=false; break; } //printf("dsa: %d\n", tmp[i+j]); } if(areEqual) return true; } } return false; } void printVector(vector<int> & v123){ for(int i = 0; i < v123.size(); i++){ printf("%d ", v123[i]); } printf("\n"); } bool numberVisited[10000]; int main(){ int n, m; scanf("%d%d", &n, &m); keys.resize(n); endValue.resize(m); for(int i = 0; i < n; i++){ int l; scanf("%d", &l); for(int j = 0; j < l; j++){ int asd; scanf("%d", &asd); keys[i].push_back(asd); numberVisited[asd]=true; } } for(int i = 0; i < m; i++){ int asd; scanf("%d", &asd); endValue[i]=asd; if(!numberVisited[asd]){ printf("-1"); return 0; } } int ctr=1; tmp = keys[0]; vector<int> tmp2; //printf("asd\n"); while(!test(tmp)){ tmp2.clear(); for(int i = 0; i < tmp.size(); i++){ for(int j = 0; j < keys[tmp[i]-1].size(); j++){ tmp2.push_back(keys[tmp[i]-1][j]); } } tmp=tmp2; //printVector(tmp); //system("pause"); ctr++; } printf("%d\n", ctr+1); }
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 | #include <cstdio> #include <algorithm> #include <vector> using namespace std; vector<vector<int> > keys; vector<int> endValue; vector<int> tmp; bool test(std::vector<int> & tmp2){ //check if tmp containts endValue //printf("tmp.size(): %d, end.size(): %d\n", tmp.size(), endValue.size()); if(tmp2.size() < endValue.size())return false; //printf("cool\n"); for(int i = 0; i < tmp2.size(); i++){ if(tmp2[i]==endValue[0]){ //printf("asd: %d\n", tmp[i]); bool areEqual=true; for(int j = 1; j < endValue.size(); j++){ if(i+j >= tmp2.size() || tmp2[i+j]!=endValue[j]){ areEqual=false; break; } //printf("dsa: %d\n", tmp[i+j]); } if(areEqual) return true; } } return false; } void printVector(vector<int> & v123){ for(int i = 0; i < v123.size(); i++){ printf("%d ", v123[i]); } printf("\n"); } bool numberVisited[10000]; int main(){ int n, m; scanf("%d%d", &n, &m); keys.resize(n); endValue.resize(m); for(int i = 0; i < n; i++){ int l; scanf("%d", &l); for(int j = 0; j < l; j++){ int asd; scanf("%d", &asd); keys[i].push_back(asd); numberVisited[asd]=true; } } for(int i = 0; i < m; i++){ int asd; scanf("%d", &asd); endValue[i]=asd; if(!numberVisited[asd]){ printf("-1"); return 0; } } int ctr=1; tmp = keys[0]; vector<int> tmp2; //printf("asd\n"); while(!test(tmp)){ tmp2.clear(); for(int i = 0; i < tmp.size(); i++){ for(int j = 0; j < keys[tmp[i]-1].size(); j++){ tmp2.push_back(keys[tmp[i]-1][j]); } } tmp=tmp2; //printVector(tmp); //system("pause"); ctr++; } printf("%d\n", ctr+1); } |