#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e9;
int n;
ll ans = inf;
vector<int> ss;
vector<vector<int>> v;
vector<int> state;
void bruteforce(int k){
if(k == n){
auto new_state = state;
for(int x: ss){
new_state[x] = !new_state[x];
for(int y: v[x]) new_state[y] = !new_state[y];
if(all_of(new_state.begin(), new_state.end(), [&](int z){return z==0;})) ans = min(ans, (ll)ss.size());
}
return;
}
ss.pb(k);
bruteforce(k+1);
ss.pop_back();
bruteforce(k+1);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
v.resize(n);
state.resize(n);
for(int i = 0; i < n-1; i++){
int a, b; cin >> a >> b; a--, b--;
v[a].pb(b);
v[b].pb(a);
}
for(int &x: state) cin >> x;
bruteforce(0);
if(ans >= inf) cout << "impossible\n";
else cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
204 KB |
Output is correct |
3 |
Correct |
174 ms |
204 KB |
Output is correct |
4 |
Correct |
175 ms |
288 KB |
Output is correct |
5 |
Correct |
189 ms |
288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
204 KB |
Output is correct |
3 |
Correct |
174 ms |
204 KB |
Output is correct |
4 |
Correct |
175 ms |
288 KB |
Output is correct |
5 |
Correct |
189 ms |
288 KB |
Output is correct |
6 |
Correct |
19 ms |
204 KB |
Output is correct |
7 |
Correct |
3 ms |
204 KB |
Output is correct |
8 |
Correct |
173 ms |
204 KB |
Output is correct |
9 |
Correct |
174 ms |
204 KB |
Output is correct |
10 |
Correct |
176 ms |
204 KB |
Output is correct |
11 |
Execution timed out |
1088 ms |
204 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1051 ms |
13244 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1098 ms |
13244 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
204 KB |
Output is correct |
3 |
Correct |
174 ms |
204 KB |
Output is correct |
4 |
Correct |
175 ms |
288 KB |
Output is correct |
5 |
Correct |
189 ms |
288 KB |
Output is correct |
6 |
Correct |
19 ms |
204 KB |
Output is correct |
7 |
Correct |
3 ms |
204 KB |
Output is correct |
8 |
Correct |
173 ms |
204 KB |
Output is correct |
9 |
Correct |
174 ms |
204 KB |
Output is correct |
10 |
Correct |
176 ms |
204 KB |
Output is correct |
11 |
Execution timed out |
1088 ms |
204 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |