oj.uz

Submission #740036

# Submission time Handle Problem Language Result Execution time Memory
740036 2023-05-12T02:06:52 Z Olympia Logičari (COCI21_logicari) C++17
50 / 110
 59 ms 33636 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 = 1000;
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) {
        //cout << color_count[1] << '\n';
        for (int i: adj[curNode]) {
            if (i != prevNode) {
                dfs (i, curNode);
            }
        }
        //cout << adj[2].size() << '\n';
        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) continue;
                        //if (cp != 1 and cc != 0) continue;
                        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 {
                        assert(cc == 0);
                        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;
                }
            }
        }
    }
    int 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]);
            }
        }
        /*
        for (int curNode = 0; curNode < (int)adj.size(); curNode++) {
            for (int i = 0; i <= 1; i++) {
                for (int j = 0; j <= 1; j++) {
                    for (int k = 0; k <= 1; k++) {
                        cout << curNode << " " << i << " " << j << " " << k << " " << dp[curNode][i][j][k] << '\n'; 
                    }
                }
            }
        }
        */
        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);
    }
    //cout << special_edge.first << " " << special_edge.second << '\n';
    int64_t mn = 1e8;
    for (int dx = 0; dx <= 1; dx++) {
        for (int dy = 0; dy <= 1; dy++) {
            //if (!(dx == 1 and dy == 0)) continue;
            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;
            //cout << myTree.color_count[1] << '\n';
            int64_t res = myTree.solve();
            //cout << res << '\n';
            mn = min(res, mn);
        }
    }
    cout << ((mn == (int)1e8) ? -1 : mn);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Runtime error 59 ms 33636 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
40.0 / 40.0

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

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Runtime error 59 ms 33636 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -