제출 #867059

#제출 시각아이디문제언어결과실행 시간메모리
867059HossamHero7The Xana coup (BOI21_xanadu)C++14
5 / 100
150 ms278788 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' void solve(){ int n; cin>>n; vector<vector<int>> adj(n); for(int i=0;i<n-1;i++){ int a,b; cin>>a>>b; a -- , b --; adj[a].push_back(b); adj[b].push_back(a); } int mask = 0; for(int i=0;i<n;i++){ int x; cin>>x; if(!x) mask |= (1<<i); } queue<int> q; vector<int> dep((1<<n),-1); q.push(mask); dep[mask] = 0; while(q.size()){ int mask = q.front(); q.pop(); for(int i=0;i<n;i++){ int nmask = mask ^ (1<<i); for(auto ch : adj[i]) nmask ^= (1<<ch); if(~dep[nmask]) continue; q.push(nmask); dep[nmask] = dep[mask] + 1; } } if(~dep[(1<<n)-1]) cout<<dep[(1<<n)-1]<<endl; else cout<<"impossible"<<endl; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } 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...