Submission #379814

#	Time	Username	Problem	Language	Result	Execution time	Memory
379814		Vimmer	Svjetlo (COCI20_svjetlo)	C++14	110 / 110	435 ms	83328 KiB

svjetlo

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define N 500500
#define NN 10000050
#define PB push_back
#define M ll(1e9 + 7)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pri(x) cout << x << endl
#define endl '\n'
#define _ << " " <<
#define F first
#define S second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
//typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

typedef long double ld;
typedef unsigned long long ull;
typedef short int si;

vector <int> g[N];

string s;

int f[N][2][3], n;

int dp[2][3];

void solve_0(int v, int u)
{
    for (int cur = 0; cur < 2; cur++)
    {
        /// he 0
        dp[cur][0] = min(dp[cur][0], f[v][cur][0] + f[u][0][0] + 3);

        /// he 1
        dp[cur ^ 1][0] = min(dp[cur ^ 1][0], f[v][cur][0] + f[u][1][0] + 1);
    }
}

void solve_1(int v, int u)
{
    for (int cur = 0; cur < 2; cur++)
    {
        dp[cur][1] = min(dp[cur][1], f[v][cur][1] + f[u][0][0] + 3);

        dp[cur ^ 1][1] = min(dp[cur ^ 1][1], f[v][cur][1] + f[u][1][0] + 1);

        dp[cur][1] = min(dp[cur][1], f[v][cur][0] + min(f[u][1][0], f[u][1][1]));
        dp[cur ^ 1][1] = min(dp[cur ^ 1][1], f[v][cur][0] + min(f[u][0][0], f[u][0][1]) + 2);
    }
}

void solve_2(int v, int u)
{
    for (int cur = 0; cur < 2; cur++)
    {
        dp[cur][2] = min(dp[cur][2], f[v][cur][2] + f[u][0][0] + 3);
        dp[cur ^ 1][2] = min(dp[cur ^ 1][2], f[v][cur][2] + f[u][1][0] + 1);

        dp[cur][2] = min(dp[cur][2], f[v][cur][0] + min(min(f[u][0][1], f[u][0][0]), f[u][0][2]) + 1);
        dp[cur ^ 1][2] = min(dp[cur ^ 1][2], f[v][cur][0] + min(min(f[u][1][0], f[u][1][1]), f[u][1][2]) + 3);

        dp[cur][2] = min(dp[cur][2], f[v][cur][1] + min(f[u][1][1], f[u][1][0]));
        dp[cur ^ 1][2] = min(dp[cur ^ 1][2], f[v][cur][1] + min(f[u][0][1], f[u][0][0]) + 2);
    }
}

void dfs(int v, int p)
{
    bool have = 0;

    for (auto it : g[v])
    {
        if (it == p) continue;

        dfs(it, v);

        if (f[it][1][0] == 0) continue;

        have = 1;
    }

    if (!have && s[v] == '1')
    {
        f[v][1][0] = 0;

        return;
    }

    f[v][1 ^ (s[v] == '1')][0] = 1;

    for (auto it : g[v])
    {
        if (it == p || f[it][1][0] == 0) continue;

        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 3; j++)
                dp[i][j] = 1e9;

        solve_0(v, it);
        solve_1(v, it);
        solve_2(v, it);

        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 3; j++)
                f[v][i][j] = dp[i][j];
    }
}

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("1.in", "r", stdin);

    for (int i = 0; i < N; i++)
        for (int t = 0; t < 2; t++)
            for (int l = 0; l < 3; l++)
                f[i][t][l] = 1e9;

    cin >> n;

    cin >> s;

    for (int i = 1; i < n; i++)
    {
        int x, y;

        cin >> x >> y;

        x--; y--;

        g[x].PB(y);

        g[y].PB(x);
    }

    for (int i = 0; i < n; i++)
    {
        if (s[i] == '1') continue;

        dfs(i, -1);

        pri(min(min(f[i][1][0], f[i][1][1]), f[i][1][2]));

        exit(0);
    }

    pri(0);
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30