#include<iostream> #include<cstdio> #include<vector> using namespace std; int drzewo[1001][500]; vector<int> index[1001]; vector<int> index2[10001]; vector<int> index3[1001]; vector<int> index4[10001]; int drzewo2[10001][500]; int v2[1000]; vector<pair<int, int> > wektor[2][1001]; int it_wek=1; bool DONE; int m; short bits[1000]; bool krok(int start, int ver_i, int ver_v){ bool b=false; //cout<<start<<" "<<ver_i<<" "<<ver_v<<endl; if(ver_v==m){ b=true; if(start){ for(int i=0;i<index3[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index3[ver_i][i],m)); b=true; } }else{ for(int i=0;i<index4[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index4[ver_i][i],m)); if(index4[ver_i][i]==0){ DONE=true; return false; } } } return true; } if(start==0){ for(int i=0;i<wektor[(it_wek-1)%2][ver_v].size();i++){ //cout<<"TUTAJ JESTEM "<<wektor[it_wek-1][ver_v][i].first<<" "<<drzewo2[ver_i][wektor[it_wek-1][ver_v][i].first]<<endl; if(drzewo2[ver_i][wektor[(it_wek-1)%2][ver_v][i].first]){ b=krok(start,drzewo2[ver_i][wektor[(it_wek-1)%2][ver_v][i].first],wektor[(it_wek-1)%2][ver_v][i].second)||b; } } if(index2[ver_i].size()){ if(bits[ver_v]==1){ b=true; for(int i=0;i<index2[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index2[ver_i][i],ver_v)); } }else if(bits[ver_v]==0){ if(krok(ver_v,0,ver_v)){ bits[ver_v]=1; b=true; for(int i=0;i<index2[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index2[ver_i][i],ver_v)); } }else{ bits[ver_v]=2; } } } }else{ if(index[ver_i].size()){ if(bits[ver_v]==1){ b=true; for(int i=0;i<index[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index[ver_i][i],ver_v)); } }else if(bits[ver_v]==0){ if(krok(ver_v,0,ver_v)){ bits[ver_v]=1; b=true; for(int i=0;i<index[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index[ver_i][i],ver_v)); } }else{ bits[ver_v]=2; } } } for(int i=0;i<wektor[(it_wek-1)%2][ver_v].size();i++){ if(drzewo[ver_i][wektor[(it_wek-1)%2][ver_v][i].first]){ b=krok(start,drzewo[ver_i][wektor[(it_wek-1)%2][ver_v][i].first],wektor[(it_wek-1)%2][ver_v][i].second)||b; } } } return b; } int main(){ int n, l; scanf("%d%d",&n,&m); int it=1; int v; int tmp; int it2=1; for(int i=0;i<n;i++){ scanf("%d",&l); v=0; for(int k=0;k<=l;k++){ v2[k]=0; } for(int j=0;j<l;j++){ scanf("%d",&tmp); tmp--; if(drzewo[v][tmp]){ v=drzewo[v][tmp]; }else{ drzewo[v][tmp]=it; v=it++; } index3[v].push_back(i); for(int k=0;k<=j;k++){ if(drzewo2[v2[k]][tmp]){ v2[k]=drzewo2[v2[k]][tmp]; }else{ drzewo2[v2[k]][tmp]=it2; v2[k]=it2++; } if(index4[v2[k]].empty()||index4[v2[k]][index4[v2[k]].size()-1]!=i){ index4[v2[k]].push_back(i); } } if(j==l-1){ index[v].push_back(i); for(int k=0;k<=j;k++){ if(index2[v2[k]].empty()||index2[v2[k]][index2[v2[k]].size()-1]!=i) index2[v2[k]].push_back(i); } } } } for(int i=0;i<m;i++){ scanf("%d",&tmp); tmp--; wektor[0][i].push_back(make_pair(tmp,i+1)); } /*for(int i=0;i<it2;i++){ cout<<i<<": "; for(int j=0;j<n;j++){ cout<<drzewo2[i][j]<<" "; } cout<<endl; }*/ while(krok(0,0,0)){ //cout<<"-----"<<endl; if(DONE) break; it_wek++; if(it_wek==100000) break; for(int i=0;i<m;i++){ bits[i]=0; wektor[it_wek%2][i].clear(); } } if(DONE) printf("%d",it_wek+1); else printf("-1"); /* for(int i=0;i<=it_wek;i++){ cout<<"IT_WEK "<<i<<endl; for(int j=0;j<m;j++){ cout<<j<<" "; for(int k=0;k<wektor[i][j].size();k++){ cout<<wektor[i][j][k].first+1<<" "; } cout<<endl; } }*/ }
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 | #include<iostream> #include<cstdio> #include<vector> using namespace std; int drzewo[1001][500]; vector<int> index[1001]; vector<int> index2[10001]; vector<int> index3[1001]; vector<int> index4[10001]; int drzewo2[10001][500]; int v2[1000]; vector<pair<int, int> > wektor[2][1001]; int it_wek=1; bool DONE; int m; short bits[1000]; bool krok(int start, int ver_i, int ver_v){ bool b=false; //cout<<start<<" "<<ver_i<<" "<<ver_v<<endl; if(ver_v==m){ b=true; if(start){ for(int i=0;i<index3[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index3[ver_i][i],m)); b=true; } }else{ for(int i=0;i<index4[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index4[ver_i][i],m)); if(index4[ver_i][i]==0){ DONE=true; return false; } } } return true; } if(start==0){ for(int i=0;i<wektor[(it_wek-1)%2][ver_v].size();i++){ //cout<<"TUTAJ JESTEM "<<wektor[it_wek-1][ver_v][i].first<<" "<<drzewo2[ver_i][wektor[it_wek-1][ver_v][i].first]<<endl; if(drzewo2[ver_i][wektor[(it_wek-1)%2][ver_v][i].first]){ b=krok(start,drzewo2[ver_i][wektor[(it_wek-1)%2][ver_v][i].first],wektor[(it_wek-1)%2][ver_v][i].second)||b; } } if(index2[ver_i].size()){ if(bits[ver_v]==1){ b=true; for(int i=0;i<index2[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index2[ver_i][i],ver_v)); } }else if(bits[ver_v]==0){ if(krok(ver_v,0,ver_v)){ bits[ver_v]=1; b=true; for(int i=0;i<index2[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index2[ver_i][i],ver_v)); } }else{ bits[ver_v]=2; } } } }else{ if(index[ver_i].size()){ if(bits[ver_v]==1){ b=true; for(int i=0;i<index[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index[ver_i][i],ver_v)); } }else if(bits[ver_v]==0){ if(krok(ver_v,0,ver_v)){ bits[ver_v]=1; b=true; for(int i=0;i<index[ver_i].size();i++){ wektor[it_wek%2][start].push_back(make_pair(index[ver_i][i],ver_v)); } }else{ bits[ver_v]=2; } } } for(int i=0;i<wektor[(it_wek-1)%2][ver_v].size();i++){ if(drzewo[ver_i][wektor[(it_wek-1)%2][ver_v][i].first]){ b=krok(start,drzewo[ver_i][wektor[(it_wek-1)%2][ver_v][i].first],wektor[(it_wek-1)%2][ver_v][i].second)||b; } } } return b; } int main(){ int n, l; scanf("%d%d",&n,&m); int it=1; int v; int tmp; int it2=1; for(int i=0;i<n;i++){ scanf("%d",&l); v=0; for(int k=0;k<=l;k++){ v2[k]=0; } for(int j=0;j<l;j++){ scanf("%d",&tmp); tmp--; if(drzewo[v][tmp]){ v=drzewo[v][tmp]; }else{ drzewo[v][tmp]=it; v=it++; } index3[v].push_back(i); for(int k=0;k<=j;k++){ if(drzewo2[v2[k]][tmp]){ v2[k]=drzewo2[v2[k]][tmp]; }else{ drzewo2[v2[k]][tmp]=it2; v2[k]=it2++; } if(index4[v2[k]].empty()||index4[v2[k]][index4[v2[k]].size()-1]!=i){ index4[v2[k]].push_back(i); } } if(j==l-1){ index[v].push_back(i); for(int k=0;k<=j;k++){ if(index2[v2[k]].empty()||index2[v2[k]][index2[v2[k]].size()-1]!=i) index2[v2[k]].push_back(i); } } } } for(int i=0;i<m;i++){ scanf("%d",&tmp); tmp--; wektor[0][i].push_back(make_pair(tmp,i+1)); } /*for(int i=0;i<it2;i++){ cout<<i<<": "; for(int j=0;j<n;j++){ cout<<drzewo2[i][j]<<" "; } cout<<endl; }*/ while(krok(0,0,0)){ //cout<<"-----"<<endl; if(DONE) break; it_wek++; if(it_wek==100000) break; for(int i=0;i<m;i++){ bits[i]=0; wektor[it_wek%2][i].clear(); } } if(DONE) printf("%d",it_wek+1); else printf("-1"); /* for(int i=0;i<=it_wek;i++){ cout<<"IT_WEK "<<i<<endl; for(int j=0;j<m;j++){ cout<<j<<" "; for(int k=0;k<wektor[i][j].size();k++){ cout<<wektor[i][j][k].first+1<<" "; } cout<<endl; } }*/ } |