Submission #1162924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162924		InvMOD	Cats or Dogs (JOI18_catdog)	C++20	38 / 100	3093 ms	6132 KiB

catdog

#include<bits/stdc++.h>

//#define name "InvMOD"
#ifndef name
    #include "catdog.h"
#endif // name

using namespace std;

template<typename T> bool ckmn(T& a, const T& b){
    if(a > b)
        return a = b, true;
    return false;
}

const int N = 1e5 + 5;

int n, dp[2][N], a[N];

vector<int> adj[N];

// brute (cat: 0, dog: 1)
int calc_dp(int x, int p){
    dp[0][x] = dp[1][x] = 0;
    if(a[x] < 2) dp[a[x] ^ 1][x] = n;

    for(int v : adj[x])if(v != p){
        calc_dp(v, x);
        dp[0][x] = dp[0][x] + min(dp[0][v], dp[1][v] + 1);
        dp[1][x] = dp[1][x] + min(dp[1][v], dp[0][v] + 1);
        ckmn(dp[0][x], n), ckmn(dp[1][x], n);
    }
    return min(dp[0][x], dp[1][x]);
}


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

    for(int i = 1; i <= n; i++) a[i] = 2;
}

int cat(int v){
    a[v] = 0;
    return calc_dp(1, -1);
}

int dog(int v){
    a[v] = 1;
    return calc_dp(1, -1);
}

int neighbor(int v){
    a[v] = 2;
    return calc_dp(1, -1);
}

#ifdef name
    int32_t main()
    {
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);

        int n; cin >> n;

        vector<int> A(n), B(n);
        for(int i = 0; i < n - 1; i++){
            cin >> A[i] >> B[i];
        }
        initialize(n, A, B);

        int q; cin >> q;
        while(q--){
            int op, v; cin >> op >> v;

            if(!op){
                cout << cat(v) << "\n";
            }
            else if(op&1) cout << dog(v) << "\n";
            else cout << neighbor(v) << "\n";
        }
        return 0;
    }
#endif // name

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