Submission #1119357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119357		Zero_OP	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3074 ms	7764 KiB

catdog

#include <bits/stdc++.h>

using namespace std;

#define dbg(x) "[" #x " = " << (x) << "]"

const int MAX = 1e5 + 5;
const int inf = 1e9;

int N;
vector<int> adj[MAX];
pair<int, int> dp[MAX]; ///[cat, dog]
int type[MAX];

void dfs(int u, int p){
    dp[u] = {MAX, MAX};
    if(type[u] == 1 || type[u] == 0) dp[u].first = 0;
    if(type[u] == 2 || type[u] == 0) dp[u].second = 0;
    for(auto v : adj[u]) if(v != p){
        dfs(v, u);
        dp[u].first += min(dp[v].first, dp[v].second + 1);
        dp[u].second += min(dp[v].first + 1, dp[v].second);
    }

    dp[u].first = min(dp[u].first, MAX);
    dp[u].second = min(dp[u].second, MAX);

//    cout << dbg(u) << dbg(dp[u].first) << dbg(dp[u].second) << '\n';
}

void initialize(int _N, vector<int> A, vector<int> B){
    N = _N;
    for(int i = 0; i < N - 1; ++i){
        int u = A[i], v = B[i];
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
}

int cat(int u){
    type[u] = 1;
    dfs(1, -1);
    return min(dp[1].first, dp[1].second);
}

int dog(int u){
    type[u] = 2;
    dfs(1, -1);
    return min(dp[1].first, dp[1].second);
}

int neighbor(int u){
    type[u] = 0;
    dfs(1, -1);
    return min(dp[1].first, dp[1].second);
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);

    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, v;
        cin >> t >> v;
        if(t == 1) cout << cat(v) << '\n';
        if(t == 2) cout << dog(v) << '\n';
        if(t == 3) cout << neighbor(v) << '\n';
    }

    return 0;
}
#endif //LOCAL

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