| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 444023 | yungyao | The Collection Game (BOI21_swaps) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
using namespace std;
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <vector>
#include <memory.h>
typedef long long LL;
typedef pair<int,int> pii;
#define F first
#define S second
#define mkp make_pair
#define iter(x) x.begin(),x.end()
#define MEM(s,e) memset(s,e,sizeof(s))
const int maxn = 1e5+100,inf = 1e9;
int dp[maxn][2][2]; //index, t/f, on/off
bool status[maxn];
vector <int> adj[maxn];
void dfs(int x,int fr){
int ldp[2][2][2],c=0;
for (auto s:adj[x]) if (s != fr){
dfs(s,x);
for (int i=0;i<2;++i) for (int j=0;j<2;++j){
ldp[c][i][j] = dp[s][i][j];
}
++c;
}
if (!c){
if (status[x]){
dp[x][1][0] = 0;
dp[x][0][1] = 1;
dp[x][0][0] = inf;
dp[x][1][1] = inf;
}
else{
dp[x][0][0] = 0;
dp[x][1][1] = 1;
dp[x][1][0] = inf;
dp[x][0][1] = inf;
}
}
else if (c == 1){
if (status[x]){
dp[x][0][0] = ldp[0][0][1];
dp[x][0][1] = ldp[0][1][0] + 1;
dp[x][1][0] = ldp[0][0][0];
dp[x][1][1] = ldp[0][1][1] + 1;
}
else{
dp[x][0][0] = ldp[0][0][0];
dp[x][0][1] = ldp[0][1][1] + 1;
dp[x][1][0] = ldp[0][0][1];
dp[x][1][1] = ldp[0][1][0] + 1;
}
}
else{
if (status[x]){
dp[x][0][0] = min(inf,min(ldp[0][0][1] + ldp[1][0][0],ldp[0][0][0] + ldp[1][0][1]));
dp[x][0][1] = min(inf,min(ldp[0][1][0] + ldp[1][1][0],ldp[0][1][1] + ldp[1][1][1]) + 1);
dp[x][1][0] = min(inf,min(ldp[0][0][0] + ldp[1][0][0],ldp[0][0][1] + ldp[1][0][1]));
dp[x][1][1] = min(inf,min(ldp[0][1][1] + ldp[1][1][0],ldp[0][1][0] + ldp[1][1][1]) + 1);
}
else{
dp[x][0][0] = min(inf,min(ldp[0][0][0] + ldp[1][0][0],ldp[0][0][1] + ldp[1][0][1]));
dp[x][0][1] = min(inf,min(ldp[0][1][1] + ldp[1][1][0],ldp[0][1][0] + ldp[1][1][1]) + 1);
dp[x][1][0] = min(inf,min(ldp[0][0][1] + ldp[1][0][0],ldp[0][0][0] + ldp[1][0][1]));
dp[x][1][1] = min(inf,min(ldp[0][1][0] + ldp[1][1][0],ldp[0][1][1] + ldp[1][1][1]) + 1);
}
}
}
int n,mxsub[maxn];
int findg(int x,int fr){
int cnt = 1;
for (auto i:adj[x]) if (i != fr){
int r = findg(i,x);
cnt += r;
mxsub[x] = max(mxsub[x],r);
}
mxsub[x] = max(mxsub[x],n - cnt);
return cnt;
}
vector <int> findans(int g,int op){
vector <int> hadj[22]; int c=0;
vector <int> ret(4,inf); //00 for f/off, 01 for f/on, 10 for t/off, 11 for t/on
bool vis[44]{};
int trs[44]{},invtrs[22]{};
queue <int> bfs; bfs.push(g); vis[g] = true;
while (bfs.size()){
int x = bfs.front(); bfs.pop();
invtrs[c] = x; trs[x] = c++;
for (auto i:adj[x]){
if (vis[i]){
hadj[trs[x]].push_back(trs[i]);
hadj[trs[i]].push_back(trs[x]);
}
else if (i != op){
bfs.push(i);
vis[i] = true;
}
}
}
for (int mask=0;mask<(1 << c);++mask){
bool stat_copy[22];
for (int i=0;i<c;++i) stat_copy[i] = status[invtrs[i]];
for (int i=0;i<c;++i) if (mask & (1 << i)){
stat_copy[i] ^= 1;
for (auto cn:hadj[i]) stat_copy[cn] ^= 1;
}
bool ok = true;
for (int i=1;i<c;++i) if (stat_copy[i]){ok = false; break;}
if (ok){
if (stat_copy[0] and (mask & 1)) ret[3] = min(ret[3],__builtin_popcount(mask));
else if (stat_copy[0] and !(mask & 1)) ret[2] = min(ret[2],__builtin_popcount(mask));
else if (!stat_copy[0] and (mask & 1)) ret[1] = min(ret[1],__builtin_popcount(mask));
else if (!stat_copy[0] and !(mask & 1)) ret[0] = min(ret[0],__builtin_popcount(mask));
}
}
return ret;
}
void brutesolve(){
findg(1,0);
int g[2],c = 0;
for (int i=1;i<=n;++i) if (mxsub[i] <= n/2) g[c++] = i;
if (c == 1) g[1] = adj[g[0]][0];
vector <int> v1 = findans(g[0],g[1]), v2 = findans(g[1],g[0]);
int ans = min(min(v1[0]+v2[0],v1[3]+v2[3]),min(v1[1]+v2[2],v1[2]+v2[1]));
if (ans >= inf) cout << "impossible\n";
else cout << ans << '\n';
}
int main(){
cin >> n;
for (int _=n-1;_--;){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i=1;i<=n;++i) cin >> status[i];
if (n <= 40) {brutesolve(); return 0;}
for (int i=1;i<=n;++i) if (adj[i].size() == 1){
dfs(i,0);
int ans = min(dp[i][0][0],dp[i][0][1]);
if (ans >= inf) cout << "impossible\n";
else cout << ans << '\n';
break;
}
return 0;
}