Submission #379463

#	Time	Username	Problem	Language	Result	Execution time	Memory
379463		Vimmer	Svjetlo (COCI20_svjetlo)	C++14	30 / 110	464 ms	79744 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 500505
#define NN 1005000
#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 tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> oredered_set;

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

int f[N][2][2], ans = 1e9;

vector <int> g[N];

string s;

void rec(int v, int p)
{
    int gd = !(s[v] == '1');

    int sum = 1;

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

        rec(it, v);

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

        if (f[it][1][0] != 1e9)
        {
            sum += f[it][1][0];
        }
        else
        {
            sum += f[it][0][0] + 2;

            gd = !gd;
        }

        gd = !gd;

        sum++;
    }

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

        return;
    }

    f[v][gd][0] = sum;
}

void dfs(int v, int p, int skok, bool clr)
{
    int sum = 1;

    if (f[v][0][0] != 1e9)
        f[v][0][1] = f[v][0][0];
            else f[v][1][1] = f[v][1][0];

    bool gd = !(s[v] == '1');

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

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

        if (f[it][1][0] != 0)
        {
            sum += f[it][1][0];
        }
        else
        {
            sum += f[it][0][0] + 2;

            gd = !gd;
        }

        gd = !gd;

        sum++;
    }

    int smr = f[v][1][0];

    bool cl = 1;

    if (smr == 1e9)
    {
        smr = f[v][0][0];

        cl = 0;
    }

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

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

        int cur = smr; /// start in v

        bool c = cl;

        cur--;

        c = !c;

        if (f[it][1][0] != 1e9)
        {
            cur -= f[it][1][0];
        }
        else
        {
            cur -= f[it][0][0] + 2;

            c = !c;
        }

        cur += skok;

        if (skok != 0)
        {
            c = !c;

            cur++;
        }

        if (clr == 0)
        {
            c = !c;

            cur += 2;
        }

        if (cur == 1 && c == 0)
        {
            c = 1;

            cur--;
        }

        dfs(it, v, cur, c);

        bool g = cl;

        int sm = smr - 1; /// start

        g = !g; /// start

        if (f[it][1][0] != 1e9)
        {
            sm -= f[it][1][0];
        }
        else
        {
            sm -= f[it][0][0] + 2;

            g = !g;
        }

        if (f[it][1][1] != 1e9)
        {
            sm += f[it][1][1];

            f[v][g][1] = min(f[v][g][1], sm);

            sm -= f[it][1][1];
        }

        if (f[it][0][1] != 1e9)
        {
            sm += f[it][0][1] + 2;

            g = !g;

            f[v][g][1] = min(f[v][g][1], sm);
        }
    }

    /// when ends in v
    {
        if (f[v][1][1] != 1e9)
        {
            smr = f[v][1][1];

            cl = 1;

            if (skok != 0)
            {
                smr += skok;

                smr++;

                cl = !cl;
            }

            if (clr == 0)
            {
                smr += 2;

                cl = !cl;
            }

            if (cl == 0 && smr == 0)
            {
                smr++;

                cl = 1;
            }

            if (cl == 1)
                ans = min(ans, smr);
        }

        if (f[v][0][1] != 1e9)
        {
            smr = f[v][0][1];

            cl = 0;

            if (skok != 0)
            {
                smr += skok;

                smr++;

                cl = !cl;
            }

            if (clr == 0)
            {
                smr += 2;

                cl = !cl;
            }

            if (cl == 0 && smr == 0)
            {
                smr++;

                cl = 1;
            }

            if (cl == 1)
                ans = min(ans, smr);
        }
    }

    /// when v is lca of x and y
    {
        int dp[2] = {int(1e9), int(1e9)}, pr[2] = {-1, -1};

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

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

            if (f[it][1][1] != 1e9 && dp[1] > f[it][1][1])
            {
                dp[1] = f[it][1][1];

                pr[1] = it;
            }

            if (f[it][0][1] != 1e9 && dp[0] > f[it][0][1])
            {
                dp[0] = f[it][0][1];

                pr[0] = it;
            }
        }

        int smt[2];

        bool color[2];

        if (f[v][1][0] != 1e9)
        {
            smt[0] = smt[1] = f[v][1][0];

            color[0] = color[1] = 1;
        }
        else
        {
            smt[0] = smt[1] = f[v][0][0];

            color[0] = color[1] = 0;
        }

        if (dp[0] != 1e9)
        {
            int it = pr[0];

            smt[0]--;   /// start

            color[0] = !color[0];

            smt[0]--;

            color[0] = !color[0];

            if (f[it][1][0] != 1e9)
            {
                smt[0] -= f[it][1][0];
            }
            else
            {
                smt[0] -= f[it][0][0] + 2;

                color[0] = !color[0];
            }
        }

        if (dp[1] != 1e9)
        {
            int it = pr[1];

            smt[1]--;

            color[1] = !color[1];

            smt[1]--;   /// start

            color[1] = !color[1];

            if (f[it][1][0] != 1e9)
            {
                smt[1] -= f[it][1][0];
            }
            else
            {
                smt[1] -= f[it][0][0] + 2;

                color[1] = !color[1];
            }
        }

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

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

            /// 0 1
            if (dp[0] != 1e9 && pr[0] != it && f[it][1][1] != 1e9)
            {
                int sum = dp[0] + f[it][1][1] + 2 + smt[0] + 1;

                /// for one 0

                /// for one step throw

                /// for maybe one step up

                bool cur = color[0];

                if (f[it][1][0] != 1e9)
                {
                    sum -= f[it][1][0];
                }
                else
                {
                    sum -= f[it][0][0] + 2;

                    cur = !cur;
                }

                sum--;

                cur = !cur;

                sum += skok;

                if (skok != 0)
                {
                    sum++;

                    cur = !cur;
                }

                if (clr == 0)
                {
                    sum += 2;

                    cur = !cur;
                }

                if (cur == 1)
                    ans = min(ans, sum);
            }

            /// 1 1

            if (dp[1] != 1e9 && pr[1] != it && f[it][1][1] != 1e9)
            {
                int sum = dp[1] + f[it][1][1] + 1 + smt[1];

                /// for one step throw

                /// for maybe one step up

                bool cur = !color[1];

                if (f[it][1][0] != 1e9)
                {
                    sum -= f[it][1][0];
                }
                else
                {
                    sum -= f[it][0][0] + 2;

                    cur = !cur;
                }

                sum--;

                cur = !cur;

                sum += skok;

                if (skok != 0)
                {
                    sum++;

                    cur = !cur;
                }

                if (clr == 0)
                {
                    sum += 2;

                    cur = !cur;
                }

                if (cur == 1)
                    ans = min(ans, sum);
            }

            /// 1 0

            if (dp[1] != 1e9 && pr[1] != it && f[it][0][1] != 1e9)
            {
                int sum = dp[1] + f[it][0][1] + 2 + 1 + smt[1];

                /// for one 0

                /// for one step throw

                /// for maybe one step up

                bool cur = color[1];

                if (f[it][1][0] != 1e9)
                {
                    sum -= f[it][1][0];
                }
                else
                {
                    sum -= f[it][0][0] + 2;

                    cur = !cur;
                }

                sum--;

                cur = !cur;

                sum += skok;

                if (skok != 0)
                {
                    sum++;

                    cur = !cur;
                }

                if (clr == 0)
                {
                    sum += 2;

                    cur = !cur;
                }

                if (cur == 1)
                    ans = min(ans, sum);
            }

            /// 0 0

            if (dp[0] != 1e9 && pr[0] != it && f[it][0][1] != 1e9)
            {
                int sum = dp[0] + f[it][0][1] + 2 + 2 + 1 + smt[0];

                /// for two 0

                /// for one step throw

                /// for maybe one step up

                bool cur = !color[0];

                if (f[it][1][0] != 1e9)
                {
                    sum -= f[it][1][0];
                }
                else
                {
                    sum -= f[it][0][0] + 2;

                    cur = !cur;
                }

                sum--;

                cur = !cur;

                sum += skok;

                if (skok != 0)
                {
                    sum++;

                    cur = !cur;
                }

                if (clr == 0)
                {
                    sum += 2;

                    cur = !cur;
                }

                if (cur == 1)
                    ans = min(ans, sum);
            }
        }
    }
}

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 r = 0; r < 2; r++)
                f[i][t][r] = 1e9;

    int n;

    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);
    }

    rec(0, -1);

    dfs(0, -1, 0, 1);

    pri(ans);
}

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