Submission #1305438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305438		dorkikann	Svjetlo (COCI20_svjetlo)	C++20	0 / 110	2 ms	968 KiB

svjetlo

#include <bits/stdc++.h>
using namespace std;

const int N = 1e2 + 5;
const int INF = 1e9;

vector<int> Graph[N];
bool Active[N];

bool Full[N];
pair<int, int> DP[N][2];

bool PreDFS(int u, int parent) 
{
    Full[u] = Active[u];
    for(auto v : Graph[u]) {
        if(v != parent)
            Full[u] &= PreDFS(v, u);
    }
    return Full[u];
}

void DFS(int u, int parent)
{
    bool ac = !Active[u];
    DP[u][0].first = 1;
    DP[u][1].first = 1;

    for(auto v : Graph[u]) {
        if(v != parent && !Full[v]) {
            DFS(v, u);

            DP[u][0].first += DP[v][0].first + 1;
            ac ^= 1;

            if(DP[v][0].second == 0) {
                DP[u][0].first += 2;
                ac ^= 1;
            }
        }
    }

    DP[u][0].second = ac;
    DP[u][1] = DP[u][0];
    if(!ac)
        DP[u][1] = {DP[u][1].first - 1, 1};

    for(auto v : Graph[u]) {
        if(v != parent && !Full[v]) {
            int val = DP[u][0].first - DP[v][0].first + DP[v][1].first - 1;
            bool ac2 = !ac;
            if(DP[v][0].second == 0) {
                val -= 2;
                ac2 = !ac2;
            }

            if(ac2)
                DP[u][1].first = min(DP[u][1].first, val);
        }
    }
}

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

    int n, a, b;
    string s;

    cin >> n >> s;
    for(int i = 0; i < n-1; i++) {
        cin >> a >> b;
        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }

    for(int i = 0; i < s.size(); i++)
        Active[i+1] = (s[i] == '1');

    int sol = INF;
    for(int i = 1; i <= n; i++) {
        PreDFS(i, 0);
        DFS(i, 0);
        sol = min(sol, DP[i][1].first);
    }    
    cout << sol;
}

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