# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
782894 | 2023-07-14T11:15:42 Z | makanhulia | The Xana coup (BOI21_xanadu) | C++17 | 1000 ms | 524288 KB |
#include<bits/stdc++.h> #define int long long using namespace std; const int MAX=1e9; int n; vector<vector<int>> adj; int cnt(int qu, int u, vector<int> c, int vis) { if(qu==n+1) return MAX; int sum=0; for(int p : c) sum+=p; if(sum==0) return 0; c[u]^=1; for(int p : adj[u]) c[p]^=1; int ret=MAX; for(int i=0; i<n; i++) { if(vis&(1 << i)) continue; ret=min(ret, 1+cnt(qu+1, i, c, vis^(1LL << i))); } return ret; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; adj.resize(n); for(int i=1; i<n; i++) { int u, v; cin >> u >> v; --u; --v; adj[u].push_back(v); adj[v].push_back(u); } vector<int> c(n); for(int &p : c) cin >> p; int ans=MAX; for(int i=0; i<n; i++) { ans=min(ans, cnt(1, i, c, (1LL << i))); } if(ans>=MAX) cout << "impossible\n"; else cout << ans << '\n'; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1078 ms | 212 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1078 ms | 212 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 835 ms | 524288 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 781 ms | 524288 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1078 ms | 212 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |