oj.uz

Submission #705555

# Submission time Handle Problem Language Result Execution time Memory
705555 2023-03-04T15:53:50 Z bebra Cats or Dogs (JOI18_catdog) C++17
38 / 100
 3000 ms 7524 KB 
// #include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


const int MAX_N = 1e5 + 5;
const int INF = 1e7;
vector<int> g[MAX_N];
// 0 - has none, 1 - has cat, 2 - has dog
int type[MAX_N];
// each connected subtree must be of one of these types
int dp[MAX_N][3];


void dfs(int v = 0, int p = -1) {
    dp[v][0] = dp[v][1] = dp[v][2] = INF;

    dp[v][type[v]] = 0;
    if (type[v] == 0) {
        dp[v][1] = dp[v][2] = 0;
    }

    for (auto u : g[v]) {
        if (u == p) continue;

        dfs(u, v);

        if (type[v] == 0) {
            dp[v][0] += min({dp[u][0], dp[u][1] + 1, dp[u][2] + 1});
            dp[v][1] += min({dp[u][0], dp[u][1], dp[u][2] + 1});
            dp[v][2] += min({dp[u][0], dp[u][1] + 1, dp[u][2]});
        } else if (type[v] == 1) {
            dp[v][1] += min({dp[u][0], dp[u][1], dp[u][2] + 1});
        } else {
            dp[v][2] += min({dp[u][0], dp[u][1] + 1, dp[u][2]});
        }
    }
}


void initialize(int n, vector<int> a, vector<int> b) {
    for (int i = 0; i < n - 1; ++i) {
        int u = a[i];
        int v = b[i];
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

int cat(int v) {
    --v;
    type[v] = 1;
    dfs();
    return min({dp[0][0], dp[0][1], dp[0][2]});
}

int dog(int v) {
    --v;
    type[v] = 2;
    dfs();
    return min({dp[0][0], dp[0][1], dp[0][2]});
}

int neighbor(int v) {
    --v;
    type[v] = 0;
    dfs();
    return min({dp[0][0], dp[0][1], dp[0][2]});
}


// int main() {
//     int n;
//     cin >> n;

//     vector<int> a(n - 1), b(n - 1);
//     for (int i = 0; i < n - 1; ++i) {
//         cin >> a[i] >> b[i];
//     }

//     initialize(n, a, b);

//     int q;
//     cin >> q;
//     while (q--) {
//         int t;
//         cin >> t;
//         int v;
//         cin >> v;
//         if (t == 1) {
//             cout << cat(v) << endl;
//         } else if (t == 2) {
//             cout << dog(v) << endl;
//         } else {
//             cout << neighbor(v) << endl;
//         }
//     }
// }

/*
5
1 2
2 3
2 4
4 5

5
1 3
2 5
1 2
2 1
3 2

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2656 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 2660 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2664 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2656 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 2660 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2664 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 11 ms 2644 KB Output is correct
18 Correct 13 ms 2668 KB Output is correct
19 Correct 8 ms 2664 KB Output is correct
20 Correct 2 ms 2656 KB Output is correct
21 Correct 3 ms 2644 KB Output is correct
22 Correct 4 ms 2644 KB Output is correct
23 Correct 16 ms 2736 KB Output is correct
24 Correct 13 ms 2668 KB Output is correct
25 Correct 7 ms 2668 KB Output is correct
26 Correct 4 ms 2644 KB Output is correct
27 Correct 3 ms 2644 KB Output is correct
28 Correct 4 ms 2644 KB Output is correct
29 Correct 17 ms 2772 KB Output is correct
30 Correct 3 ms 2644 KB Output is correct
31 Correct 3 ms 2644 KB Output is correct
32 Correct 4 ms 2644 KB Output is correct

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2656 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 2660 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2664 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 11 ms 2644 KB Output is correct
18 Correct 13 ms 2668 KB Output is correct
19 Correct 8 ms 2664 KB Output is correct
20 Correct 2 ms 2656 KB Output is correct
21 Correct 3 ms 2644 KB Output is correct
22 Correct 4 ms 2644 KB Output is correct
23 Correct 16 ms 2736 KB Output is correct
24 Correct 13 ms 2668 KB Output is correct
25 Correct 7 ms 2668 KB Output is correct
26 Correct 4 ms 2644 KB Output is correct
27 Correct 3 ms 2644 KB Output is correct
28 Correct 4 ms 2644 KB Output is correct
29 Correct 17 ms 2772 KB Output is correct
30 Correct 3 ms 2644 KB Output is correct
31 Correct 3 ms 2644 KB Output is correct
32 Correct 4 ms 2644 KB Output is correct
33 Execution timed out 3046 ms 7524 KB Time limit exceeded
34 Halted 0 ms 0 KB -