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 <cstdlib> // For std::exit()
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);
}
}
for (int i = 0; i < n; i++)
{
queue<pair<int, ull>> q;
q.push(make_pair(i, state));
int level = 0;
while (!q.empty() && level < 15)
{
int q_size = q.size();
for (int j = 0; j < q_size; ++j)
{
auto front = q.front();
q.pop();
int node = front.first;
ull current_state = front.second;
if (current_state == 0)
{
cout << level << endl;
return 0;
}
current_state ^= (1ULL << node);
for (int neighbor : adj[node])
{
current_state ^= (1ULL << neighbor);
}
for (int k = 0; k < n; ++k)
{
if (k != node)
{
q.push(make_pair(k, current_state));
}
}
}
++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... |