Submission #759450

#	Time	Username	Problem	Language	Result	Execution time	Memory
759450		Hanksburger	The Xana coup (BOI21_xanadu)	C++17	100 / 100	65 ms	18460 KiB

xanadu

#include <bits/stdc++.h>
#define big (int)1e9
using namespace std;
int dp[100005][2][2], a[100005];
vector<int> adj[100005];
void dfs(int u, int p)
{
    for (int v:adj[u])
        if (v!=p)
            dfs(v, u);
    if (adj[u].size()==1 && p)
    {
        if (a[u])
        {
            dp[u][1][0]=big;
            dp[u][0][1]=big;
            dp[u][0][0]=0;
            dp[u][1][1]=1;
        }
        else
        {
            dp[u][1][0]=0;
            dp[u][0][1]=1;
            dp[u][0][0]=big;
            dp[u][1][1]=big;
        }
//        cout << "u=" << u << ": " << dp[u][1][0] << ' ' << dp[u][0][1] << ' ' << dp[u][0][0] << ' ' << dp[u][1][1] << '\n';
        return;
    }
    int x1, x2, x3, x4, start=0;
    for (int v:adj[u])
    {
        if (v==p)
            continue;
        if (start)
        {
            int y1=min(x1+dp[v][1][0], x3+dp[v][1][1]);
            int y2=min(x2+dp[v][0][0], x4+dp[v][0][1]);
            int y3=min(x3+dp[v][1][0], x1+dp[v][1][1]);
            int y4=min(x4+dp[v][0][0], x2+dp[v][0][1]);
            x1=min(y1, big);
            x2=min(y2, big);
            x3=min(y3, big);
            x4=min(y4, big);
        }
        else
        {
            x1=dp[v][1][a[u]];
            x2=dp[v][0][a[u]];
            x3=dp[v][1][!a[u]];
            x4=dp[v][0][!a[u]];
            start=1;
        }
    }
    dp[u][1][0]=x1;
    dp[u][0][1]=x2+1;
    dp[u][0][0]=x3;
    dp[u][1][1]=x4+1;
//    cout << "u=" << u << ": " << dp[u][1][0] << ' ' << dp[u][0][1] << ' ' << dp[u][0][0] << ' ' << dp[u][1][1] << '\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i=1; i<=n; i++)
        cin >> a[i];
    dfs(1, 0);
    if (min(dp[1][1][0], dp[1][1][1])>big/2)
        cout << "impossible";
    else
        cout << min(dp[1][1][0], dp[1][1][1]);
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:58:19: warning: 'x4' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |     dp[u][1][1]=x4+1;
      |                 ~~^~
xanadu.cpp:57:16: warning: 'x3' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |     dp[u][0][0]=x3;
      |     ~~~~~~~~~~~^~~
xanadu.cpp:56:19: warning: 'x2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |     dp[u][0][1]=x2+1;
      |                 ~~^~
xanadu.cpp:55:16: warning: 'x1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |     dp[u][1][0]=x1;
      |     ~~~~~~~~~~~^~~

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