oj.uz

Submission #740037

# Submission time Handle Problem Language Result Execution time Memory
740037 2023-05-12T02:08:14 Z Olympia Logičari (COCI21_logicari) C++17
110 / 110
 192 ms 23748 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 5 ms 6484 KB Output is correct
3 Correct 5 ms 6484 KB Output is correct
4 Correct 5 ms 6484 KB Output is correct
5 Correct 185 ms 22880 KB Output is correct
6 Correct 178 ms 23748 KB Output is correct
7 Correct 192 ms 21284 KB Output is correct
8 Correct 182 ms 21896 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 5 ms 6484 KB Output is correct
3 Correct 5 ms 6484 KB Output is correct
4 Correct 5 ms 6484 KB Output is correct
5 Correct 5 ms 6484 KB Output is correct
6 Correct 5 ms 6484 KB Output is correct
7 Correct 4 ms 6484 KB Output is correct
8 Correct 5 ms 6484 KB Output is correct
9 Correct 4 ms 6484 KB Output is correct
10 Correct 5 ms 6484 KB Output is correct
11 Correct 5 ms 6484 KB Output is correct
12 Correct 5 ms 6484 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 5 ms 6484 KB Output is correct
3 Correct 5 ms 6484 KB Output is correct
4 Correct 5 ms 6484 KB Output is correct
5 Correct 5 ms 6484 KB Output is correct
6 Correct 5 ms 6484 KB Output is correct
7 Correct 4 ms 6484 KB Output is correct
8 Correct 5 ms 6484 KB Output is correct
9 Correct 4 ms 6484 KB Output is correct
10 Correct 5 ms 6484 KB Output is correct
11 Correct 5 ms 6484 KB Output is correct
12 Correct 5 ms 6484 KB Output is correct
13 Correct 5 ms 6612 KB Output is correct
14 Correct 5 ms 6640 KB Output is correct
15 Correct 5 ms 6612 KB Output is correct
16 Correct 5 ms 6612 KB Output is correct
17 Correct 4 ms 6484 KB Output is correct
18 Correct 5 ms 6612 KB Output is correct
19 Correct 4 ms 6584 KB Output is correct
20 Correct 6 ms 6612 KB Output is correct
21 Correct 5 ms 6612 KB Output is correct
22 Correct 5 ms 6612 KB Output is correct
23 Correct 5 ms 6612 KB Output is correct
24 Correct 5 ms 6612 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 5 ms 6484 KB Output is correct
3 Correct 5 ms 6484 KB Output is correct
4 Correct 5 ms 6484 KB Output is correct
5 Correct 185 ms 22880 KB Output is correct
6 Correct 178 ms 23748 KB Output is correct
7 Correct 192 ms 21284 KB Output is correct
8 Correct 182 ms 21896 KB Output is correct
9 Correct 5 ms 6484 KB Output is correct
10 Correct 5 ms 6484 KB Output is correct
11 Correct 5 ms 6484 KB Output is correct
12 Correct 5 ms 6484 KB Output is correct
13 Correct 5 ms 6484 KB Output is correct
14 Correct 5 ms 6484 KB Output is correct
15 Correct 4 ms 6484 KB Output is correct
16 Correct 5 ms 6484 KB Output is correct
17 Correct 4 ms 6484 KB Output is correct
18 Correct 5 ms 6484 KB Output is correct
19 Correct 5 ms 6484 KB Output is correct
20 Correct 5 ms 6484 KB Output is correct
21 Correct 5 ms 6612 KB Output is correct
22 Correct 5 ms 6640 KB Output is correct
23 Correct 5 ms 6612 KB Output is correct
24 Correct 5 ms 6612 KB Output is correct
25 Correct 4 ms 6484 KB Output is correct
26 Correct 5 ms 6612 KB Output is correct
27 Correct 4 ms 6584 KB Output is correct
28 Correct 6 ms 6612 KB Output is correct
29 Correct 5 ms 6612 KB Output is correct
30 Correct 5 ms 6612 KB Output is correct
31 Correct 5 ms 6612 KB Output is correct
32 Correct 5 ms 6612 KB Output is correct
33 Correct 111 ms 13264 KB Output is correct
34 Correct 128 ms 13192 KB Output is correct
35 Correct 140 ms 13268 KB Output is correct
36 Correct 131 ms 13376 KB Output is correct
37 Correct 35 ms 8276 KB Output is correct
38 Correct 125 ms 13280 KB Output is correct
39 Correct 12 ms 7104 KB Output is correct
40 Correct 124 ms 13160 KB Output is correct
41 Correct 85 ms 14232 KB Output is correct
42 Correct 84 ms 14312 KB Output is correct
43 Correct 174 ms 21304 KB Output is correct
44 Correct 141 ms 19644 KB Output is correct