Submission #1106184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106184		alexdd	The Xana coup (BOI21_xanadu)	C++17	100 / 100	84 ms	18772 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
int n;
vector<int> con[100005];
int dp[100005][2][2];//dp[nod][stare_nod][insus]
int a[100005];
void dfs(int nod, int par)
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            dp[nod][i][j]=INF;
    dp[nod][a[nod]][0]=0;
    dp[nod][1-a[nod]][1]=1;
    for(int adj:con[nod])
    {
        if(adj==par)
            continue;
        dfs(adj,nod);
        int old[2][2];
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                old[i][j]=dp[nod][i][j];
        for(int v=0;v<2;v++)
        {
            dp[nod][v][0] = min({INF, old[v][0]+dp[adj][0][0], old[1-v][0]+dp[adj][0][1]});
            dp[nod][v][1] = min({INF, old[v][1]+dp[adj][1][0], old[1-v][1]+dp[adj][1][1]});
        }
    }
}
signed main()
{
    cin>>n;
    int u,v;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        con[u].push_back(v);
        con[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dfs(1,0);
    int rez = min(dp[1][0][0], dp[1][0][1]);
    if(rez>=INF)
        cout<<"impossible";
    else
        cout<<rez;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40
• Subtask 5: 30 / 30