Submission #740037

#	Time	Username	Problem	Language	Result	Execution time	Memory
740037		Olympia	Logičari (COCI21_logicari)	C++17	110 / 110	192 ms	23748 KiB

Main

#include <iostream>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <map>
#include <deque>
#include <stdio.h>
using namespace std; 
struct DisjointSetUnion {
    vector<int> parent;
    vector<int> sz;
    void join (int u, int v) {
        u = find_head(u), v = find_head(v);
        if (u == v) {
            return;
        }
        if (sz[u] > sz[v]) {
            swap(u, v);
        }
        parent[u] = v;
        sz[v] += sz[u];
    }
    int find_head (int x) {
        return ((x == parent[x]) ? x : find_head(parent[x]));
    }
    DisjointSetUnion (int n) {
        for (int i = 0; i < n; i++) {
            parent.push_back(i), sz.push_back(1);
        }
    }
};
const int MX = 100000;
struct Tree {
    vector<vector<int>> adj;
    int64_t dp[MX][2][2][2];
    //dp[node][colors of parent][color of me][sum of colors of children]
    map<int,int> color;
    map<int,int> color_count;
    void dfs (int curNode, int prevNode) {
        for (int i: adj[curNode]) {
            if (i != prevNode) {
                dfs (i, curNode);
            }
        }
        for (int cp = 0; cp <= 1; cp++) { //is the parent (prevNode) blue eyed or not?
            for (int cm = 0; cm <= 1; cm++) { //is curNode blue eyed or not?
                for (int cc = 0; cc <= 1; cc++) { //how many children of curNode are blue-eyed (at most 1)
                    if (cc == 1 and cp == 1) {
                        continue;
                    }
                    if (curNode == 0 and cp != 0) {
                        continue;
                    }
                    if (color_count.count(curNode) and cc + cp != color_count[curNode]) {
                        continue;
                    }
                    if (!color_count.count(curNode) and cc + cp != 1) {
                        continue;
                    }
                    if (color.count(curNode) and cm != color[curNode]) {
                        continue;
                    }
                    if (adj[curNode].size() == 1 and curNode != 0) {
                        if (cc == 0) {
                            dp[curNode][cp][cm][cc] = (cm == 1);
                        }
                        continue;
                    }
                    if (cc == 1) {
                        int64_t sum = (cm == 1);
                        for (int i: adj[curNode]) {
                            if (i != prevNode) {
                                sum += min(dp[i][cm][0][0], dp[i][cm][0][1]);
                            }
                        }
                        for (int i: adj[curNode]) {
                            if (i != prevNode) {
                                dp[curNode][cp][cm][cc] = min(dp[curNode][cp][cm][cc], sum - min(dp[i][cm][0][0], dp[i][cm][0][1]) + min(dp[i][cm][1][0], dp[i][cm][1][1]));
                            }
                        }
                    } else {
                        dp[curNode][cp][cm][cc] = (cm == 1);
                        for (int i: adj[curNode]) {
                            if (i != prevNode) {
                                dp[curNode][cp][cm][cc] += min(dp[i][cm][0][0], dp[i][cm][0][1]);
                            }
                        }
                    }
                }
            }
        }
    }
    void clear () {
        for (int i = 0; i < MX; i++) {
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 1; k++) {
                    dp[i][j][k][0] = 1e8;
                    dp[i][j][k][1] = 1e8;
                }
            }
        }
    }
    int64_t solve () {
        clear();
        dfs(0, 0);
        int64_t mn = 1e8;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 1; k++) {
                mn = min(mn, dp[0][0][j][k]);
            }
        }
        color.clear();
        color_count.clear();
        return mn;
    }
    void add_edge (int u, int v) {
        adj[u].push_back(v), adj[v].push_back(u);
    }
    Tree (int n) {
        adj.resize(n);
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    DisjointSetUnion dsu(n);
    Tree myTree(n);
    pair<int,int> special_edge;
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        if (dsu.find_head(u) == dsu.find_head(v)) {
            special_edge = make_pair(u, v);
            continue;
        }
        myTree.add_edge(u, v);
        dsu.join(u, v);
    }
    int64_t mn = 1e8;
    for (int dx = 0; dx <= 1; dx++) {
        for (int dy = 0; dy <= 1; dy++) {
            myTree.color[special_edge.first] = dx;
            myTree.color_count[special_edge.first] = 1 - dy;
            myTree.color[special_edge.second] = dy;
            myTree.color_count[special_edge.second] = 1 - dx;
            mn = min(myTree.solve(), mn);
        }
    }
    cout << ((mn == (int)1e8) ? -1 : mn);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40
• Subtask 4: 50 / 50