This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n,u,v,dfsorder[100005],dp[100005][5][5],ans1,ans2,a[100005];
//first 0 1 closed?
//second 0 1 pressed?
vector <int> edge[100005],v1,v2;
bool vis[100005];
queue <int> q;
void dfs(int x){
vis[x]=true;
for (int i=0;i<edge[x].size();i++){
if (!vis[edge[x][i]]){
dfsorder[x]++;
dfs(edge[x][i]);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin >> n;
for (int i=1;i<n;i++){
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
for (int i=1;i<=n;i++){
cin >> a[i];
}
dfs(1);
for (int i=1;i<=n;i++){
if (dfsorder[i] == 0)
q.push(i);
vis[i]=false;
dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=1e9;
}
while (!q.empty()){
u=q.front(); q.pop(); vis[u]=true;
ans1=ans2=0; v1.clear(); v2.clear();
for (int i=0;i<edge[u].size();i++){
if (vis[edge[u][i]]){
ans1+=dp[edge[u][i]][0][0]; // off
v1.push_back(dp[edge[u][i]][0][1]-dp[edge[u][i]][0][0]);
ans2+=dp[edge[u][i]][1][0]; // on
v2.push_back(dp[edge[u][i]][1][1]-dp[edge[u][i]][1][0]);
}
else
{
dfsorder[edge[u][i]]--;
if (dfsorder[edge[u][i]] == 0)
q.push(edge[u][i]);
}
}
dp[u][a[u]][0]=min(ans1,dp[u][a[u]][0]); dp[u][1-a[u]][1]=min(ans2+1,dp[u][1-a[u]][1]);
sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end());
for (int i=0;i<v1.size();i++){
ans1+=v1[i]; ans2+=v2[i];
if (i%2 == 0){
dp[u][1-a[u]][0]=min(dp[u][1-a[u]][0],ans1);
dp[u][a[u]][1]=min(dp[u][a[u]][1],ans2+1);
}
else
{
dp[u][a[u]][0]=min(dp[u][a[u]][0],ans1);
dp[u][1-a[u]][1]=min(dp[u][1-a[u]][1],ans2+1);
}
}
}
if (min(dp[1][0][0],dp[1][0][1]) >= 1e9)
cout << "impossible\n";
else
cout << min(dp[1][0][0],dp[1][0][1]) << "\n";
return 0;
}
//1 3 6 10
//2 7 9
//4 5 11
//8
Compilation message (stderr)
xanadu.cpp: In function 'void dfs(int)':
xanadu.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for (int i=0;i<edge[x].size();i++){
| ~^~~~~~~~~~~~~~~
xanadu.cpp: In function 'int main()':
xanadu.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i=0;i<edge[u].size();i++){
| ~^~~~~~~~~~~~~~~
xanadu.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i=0;i<v1.size();i++){
| ~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |