Submission #1162922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162922		InvMOD	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	2 ms	2632 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 = 0; 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);
}

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