제출 #986226

#제출 시각아이디문제언어결과실행 시간메모리
986226dorjderemThe Xana coup (BOI21_xanadu)C++17
0 / 100
517 ms524288 KiB
#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 < 20) { 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...