Submission #705514

#	Time	Username	Problem	Language	Result	Execution time	Memory
705514		bebra	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	1 ms	2644 KiB

catdog

#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 dp[0][1];
}

int dog(int v) {
    --v;
    type[v] = 2;
    dfs();
    return 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) << '\n';
//         } else if (t == 2) {
//             cout << dog(v) << '\n';
//         } else {
//             cout << neighbor(v) << '\n';
//         }
//     }
// }

/*
5
1 2
2 3
2 4
4 5

5
1 3
2 5
1 2
2 1
3 2

*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62