제출 #867062

#제출 시각아이디문제언어결과실행 시간메모리
867062HossamHero7The Xana coup (BOI21_xanadu)C++14
15 / 100
70 ms7516 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' int n; vector<bool> on; int solve(int i,bool change,bool need){ if(i == n) return (need ? 1e9 : 0); if(need) return solve(i+1,1,on[i]^change^1) + 1; return solve(i+1,0,on[i]^change); } void solve(){ 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); } if(n <= 20){ 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; } else { on.resize(n); for(int i=0;i<n;i++){ int x;cin>>x; if(x) on[i] = 1; } int ans = solve(0,0,0); if(ans >= 1e9) cout<<"impossible"<<endl; else cout<<ans<<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...