Submission #758425

#	Time	Username	Problem	Language	Result	Execution time	Memory
758425		anaduguleanu	The Xana coup (BOI21_xanadu)	C++14	100 / 100	72 ms	23936 KiB

xanadu

#include <iostream>
#include <vector>
#define MAX 100000
#define INF 1000000000
using namespace std;
///ifstream cin ("c.in");
///ofstream cout ("c.out");
int status[MAX + 10];
long long DP[MAX + 10][3][3];
vector <int> graph[MAX + 10];
void dfs(int node, int parent)
{
    long long dp[3][3];
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[1][0] = INF;
    dp[1][1] = INF;
    for (auto next : graph[node])
        if (next != parent)
        {
            dfs(next, node);
            long long aux[3][3];
            aux[0][0] = dp[0][0];
            aux[0][1] = dp[0][1];
            aux[1][0] = dp[1][0];
            aux[1][1] = dp[1][1];
            dp[0][0] = min(aux[0][0] + DP[next][0][0], aux[1][0] + DP[next][1][0]);
            dp[0][1] = min(aux[0][1] + DP[next][0][1], aux[1][1] + DP[next][1][1]);
            dp[1][0] = min(aux[0][0] + DP[next][1][0], aux[1][0] + DP[next][0][0]);
            dp[1][1] = min(aux[0][1] + DP[next][1][1], aux[1][1] + DP[next][0][1]);
        }
    if (status[node] == 1)
    {
        DP[node][0][0] = dp[1][0];
        DP[node][0][1] = dp[0][0];
        DP[node][1][0] = dp[0][1] + 1;
        DP[node][1][1] = dp[1][1] + 1;
    }
    else
    {
        DP[node][0][0] = dp[0][0];
        DP[node][0][1] = dp[1][0];
        DP[node][1][0] = dp[1][1] + 1;
        DP[node][1][1] = dp[0][1] + 1;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        cin >> status[i];
    dfs(1, 0);
    long long ans = min(DP[1][0][0], DP[1][1][0]);
    if (ans <= n)
        cout << ans;
    else
        cout << "impossible";
    return 0;
}

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