oj.uz

Submission #1013286

# Submission time Handle Problem Language Result Execution time Memory
1013286 2024-07-03T11:21:00 Z atom Logičari (COCI21_logicari) C++17
110 / 110
 107 ms 35160 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

#define int long long

struct DisJointSet {
    int n;
    vector <int> pa, sz;
    DisJointSet(int _n) {
        n = _n;
        pa.resize(n + 5);
        sz.resize(n + 5);
        for (int i = 1; i <= n; ++i) {
           pa[i] = i;
           sz[i] = 1;
        }
    }
    int get(int u) { return (u == pa[u]? u : pa[u] = get(pa[u])); }
    bool unite(int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) return 0;
        if (sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        pa[v] = u;
        return 1;
    }
};

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

vector <int> adj[N];
int st, en;
int ans;

int dp[N][2][2][2][2];
// dp(x, self, pa, root, end) : 
// number of 1 nodes in x's subtree with color self, color of parent self, color of root, color of other root: end 

int dfs(int u, int p, bool self, bool pa, bool root, bool end) {
    if (dp[u][self][pa][root][end] != -1) 
        return dp[u][self][pa][root][end];

    // invalid case
    bool invalid = false;
    if (u == st && root != self) invalid = true;
    if (u == en && end != self) invalid = true;
    if (u == en && pa == 1 && root == 1) invalid = true;

    if (invalid) 
        return dp[u][self][pa][root][end] = INF;

    int res = INF;

    bool must = false; // handle case when current node having adjacent one 1-node
    if (pa) must = true;
    if (u == st && end == 1) must = true;
    if (u == en && root == 1) must = true;

    int sum = 0;
    if (self) ++sum;
    // must = 1 -> u only takes result from 0-node child
    for (int v : adj[u]) {
        if (v == p) continue;
        sum += dfs(v, u, 0, self, root, end);
    }
    if (must)
        res = min(res, sum);
    // must = 0 -> fix one child by 1, others by 0
    if (!must) {
        for (int v : adj[u]) {
            if (v == p) continue;
            int cur = sum - dfs(v, u, 0, self, root, end) + dfs(v, u, 1, self, root, end);
            res = min(res, cur);
        }
    }

    if (res > INF) res = INF;
    return dp[u][self][pa][root][end] = res;
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    #ifdef JASPER
       freopen("in1", "r", stdin);
    #endif

    int n; cin >> n;
    DisJointSet dsu(n);

    
    for (int i = 1; i <= n; ++i) {
        int u, v; 
        cin >> u >> v;

        if (!dsu.unite(u, v)) {
            st = u;
            en = v;
        }
        else {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }

    if (st > en) swap(st, en);

    debug(st, en);

    ans = INF;
    for (int i = 0; i <= 1; ++i) {
        for (int j = 0; j <= 1; ++j) {
            memset(dp, -1, sizeof dp);  
            ans = min(ans, dfs(st, 0, i, 0, i, j));
        }
    }

    if (ans == INF) ans = -1;
    cout << ans << "\n";


    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 166
      |                    ^~~
Main.cpp:118:5: note: in expansion of macro 'debug'
  118 |     debug(st, en);
      |     ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 3 ms 15196 KB Output is correct
5 Correct 87 ms 34104 KB Output is correct
6 Correct 96 ms 34104 KB Output is correct
7 Correct 94 ms 33880 KB Output is correct
8 Correct 107 ms 34128 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
40.0 / 40.0

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

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 3 ms 15196 KB Output is correct
5 Correct 87 ms 34104 KB Output is correct
6 Correct 96 ms 34104 KB Output is correct
7 Correct 94 ms 33880 KB Output is correct
8 Correct 107 ms 34128 KB Output is correct
9 Correct 3 ms 15196 KB Output is correct
10 Correct 3 ms 15196 KB Output is correct
11 Correct 3 ms 15196 KB Output is correct
12 Correct 3 ms 15196 KB Output is correct
13 Correct 3 ms 15196 KB Output is correct
14 Correct 3 ms 15196 KB Output is correct
15 Correct 3 ms 15196 KB Output is correct
16 Correct 3 ms 15196 KB Output is correct
17 Correct 3 ms 15196 KB Output is correct
18 Correct 3 ms 15196 KB Output is correct
19 Correct 3 ms 15192 KB Output is correct
20 Correct 3 ms 15196 KB Output is correct
21 Correct 4 ms 15196 KB Output is correct
22 Correct 3 ms 15192 KB Output is correct
23 Correct 4 ms 15196 KB Output is correct
24 Correct 3 ms 15196 KB Output is correct
25 Correct 4 ms 15196 KB Output is correct
26 Correct 3 ms 15196 KB Output is correct
27 Correct 3 ms 15196 KB Output is correct
28 Correct 4 ms 15280 KB Output is correct
29 Correct 4 ms 15196 KB Output is correct
30 Correct 3 ms 15196 KB Output is correct
31 Correct 3 ms 15452 KB Output is correct
32 Correct 3 ms 15412 KB Output is correct
33 Correct 55 ms 21000 KB Output is correct
34 Correct 54 ms 20828 KB Output is correct
35 Correct 53 ms 20828 KB Output is correct
36 Correct 55 ms 20824 KB Output is correct
37 Correct 16 ms 16768 KB Output is correct
38 Correct 58 ms 21064 KB Output is correct
39 Correct 7 ms 15708 KB Output is correct
40 Correct 59 ms 20968 KB Output is correct
41 Correct 28 ms 21712 KB Output is correct
42 Correct 30 ms 21832 KB Output is correct
43 Correct 83 ms 35160 KB Output is correct
44 Correct 57 ms 28368 KB Output is correct