#include <bits/stdc++.h> using namespace std; bool wynik=0; int n; vector <pair<int,int> > e; set<vector<bool> > bity; void rekur(vector <bool>& b){ bity.insert(b); /*for (int i=0; i<n;i++){ cout << b[i]; } cout << ";"<<endl;*/ for (int i=0; i<e.size();i++){ bool tmp1=b[e[i].first]; bool tmp2=b[e[i].second]; //cout << tmp1<<" "<<tmp2<<" "<<e[i].first<<" "<<e[i].second<<endl; b[e[i].first]=tmp2; if (bity.find(b)==bity.end()){ rekur(b); } b[e[i].first]=tmp1; b[e[i].second]=tmp1; if (bity.find(b)==bity.end()){ rekur(b); } b[e[i].second]=tmp2; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int z; cin >> z; for (int z2=0; z2<z;z2++){ cin >> n; e.clear(); bity.clear(); vector <bool> kol; vector <bool> koloczekiwane; for (int i=0; i<n;i++){ char tmp; cin >> tmp; kol.push_back(tmp=='1'); } for (int i=0; i<n;i++){ char tmp; cin >> tmp; koloczekiwane.push_back(tmp=='1'); } for (int i=0; i<n-1;i++){ int tmp1,tmp2; cin >> tmp1>>tmp2; tmp1--; tmp2--; e.push_back(make_pair(tmp1,tmp2)); } rekur(kol); if (bity.find(koloczekiwane)!=bity.end()){ cout << "TAK"<<endl; }else{ cout << "NIE"<<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 | #include <bits/stdc++.h> using namespace std; bool wynik=0; int n; vector <pair<int,int> > e; set<vector<bool> > bity; void rekur(vector <bool>& b){ bity.insert(b); /*for (int i=0; i<n;i++){ cout << b[i]; } cout << ";"<<endl;*/ for (int i=0; i<e.size();i++){ bool tmp1=b[e[i].first]; bool tmp2=b[e[i].second]; //cout << tmp1<<" "<<tmp2<<" "<<e[i].first<<" "<<e[i].second<<endl; b[e[i].first]=tmp2; if (bity.find(b)==bity.end()){ rekur(b); } b[e[i].first]=tmp1; b[e[i].second]=tmp1; if (bity.find(b)==bity.end()){ rekur(b); } b[e[i].second]=tmp2; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int z; cin >> z; for (int z2=0; z2<z;z2++){ cin >> n; e.clear(); bity.clear(); vector <bool> kol; vector <bool> koloczekiwane; for (int i=0; i<n;i++){ char tmp; cin >> tmp; kol.push_back(tmp=='1'); } for (int i=0; i<n;i++){ char tmp; cin >> tmp; koloczekiwane.push_back(tmp=='1'); } for (int i=0; i<n-1;i++){ int tmp1,tmp2; cin >> tmp1>>tmp2; tmp1--; tmp2--; e.push_back(make_pair(tmp1,tmp2)); } rekur(kol); if (bity.find(koloczekiwane)!=bity.end()){ cout << "TAK"<<endl; }else{ cout << "NIE"<<endl; } } } |