-
Notifications
You must be signed in to change notification settings - Fork 0
/
test.cpp
100 lines (89 loc) · 1.86 KB
/
test.cpp
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
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int n;
const int maxn = 1000005;
vector<vector<int> > next;
vector<bool> was;
vector<bool> was2;
bool adj(int a, int b){
for(int i=0; i<next[a].size(); i++) {
if(next[a][i] == b) return true;
}
return false;
}
bool cango(int f, int to) {
if(f == to) return false;
if(adj(f,to)) return true;
for(int i=0; i<next[f].size(); i++) {
if(adj(next[f][i], to)) return true;
}
return false;
}
bool wash[maxn];
bool hamilton(int cur) {
if(cur == n) {
bool finish = true;
for(int i=1; i<n; i++){
if(!wash[i]) { finish = false; break; }
}
return finish;
}
wash[cur] = true;
bool wyn = false;
for(int i=1; i<=n; i++){
if(!wash[i] && cango(cur, i)) {
if(hamilton(i)) {
wyn = true;
break;
}
}
}
wash[cur] = false;
return wyn;
}
int main() {
cin >> n;
next.resize(n+1);
was .resize(n+1);
was2.resize(n+1);
for(int i=0; i<n-1; i++) {
int a,b;
cin >> a >> b;
next[a].push_back(b);
next[b].push_back(a);
}
string line1;
cin >> line1;
if(line1 == "1") {
was2[1] = true;
if(n<16 && !hamilton(1)) {
cerr << " !!!!!! " << endl;
return 1;
}
} else if(line1 == "BRAK") {
cerr << " * BRAK * " << endl;
if(hamilton(1)) {
cerr << " !!!!!! " << endl;
return 1;
}
else return 0;
}
int current = 1;
for(int i=1; i<n; i++) {
int a;
cin >> a;
if(i==n-1 && a!=n) { cerr << "line "<<n << endl; return 1; }
else {
if(!cango(current, a)) { cerr << "cannot go " << current << "->" << a << endl; return 1; }
current = a;
}
if(was2[current]) { cerr << "was "<< current << endl; return 1; }
was2[current] = true;
}
for(int i=0; i<n; i++) {
if(was2[i+1] == false) cerr << "was not " << i+1 << endl;
}
return 0;
}