This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <bitset>
using namespace std;
#define ull unsigned long long
int main()
{
int n;
cin >> n;
vector<vector<int>> adj(n);
int a, b;
for (int i = 0; i < n - 1; ++i)
{
cin >> a >> b;
--a;
--b;
adj[a].push_back(b);
adj[b].push_back(a);
}
ull state = 0;
for (int i = 0; i < n; ++i)
{
int temp;
cin >> temp;
if (temp == 1)
{
state |= (1ULL << i);
}
}
queue<tuple<int, ull, ull>> q;
for (int i = 0; i < n; i++)
q.push(make_tuple(i, state, 0));
int level = 0;
while (!q.empty() && level <= n)
{
int q_size = q.size();
for (int j = 0; j < q_size; ++j)
{
auto [node, current_state, visited_bits] = q.front();
q.pop();
if (current_state == 0)
{
cout << level << endl;
return 0;
}
ull temp_state = current_state;
temp_state ^= (1ULL << node);
for (ull nxt : adj[node])
{
temp_state ^= (1ULL << nxt);
}
for (int k = 0; k < n; k++)
{
if ((visited_bits & (1ULL << k)) == 0)
{
int temp_vis = visited_bits;
temp_vis |= (1 << k);
q.push(make_tuple(k, temp_state, temp_vis));
}
}
}
++level;
}
cout << "IMPOSSIBLE" << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |