Submission #302582

#	Time	Username	Problem	Language	Result	Execution time	Memory
302582		gevacrt	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3055 ms	8712 KiB

catdog

#include<bits/stdc++.h>
#include "catdog.h"
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()


int N; vi col;
vvi adj, dp;

void dfs(int u, int p){
    dp[u][0] = dp[u][1] = dp[u][2] = 0;
    for(auto v : adj[u]){
        if(v == p) continue;
        dfs(v, u);
        dp[u][0] += min({dp[v][0], dp[v][1]+1, dp[v][2]+1});
        dp[u][1] += min({dp[v][0], dp[v][1], dp[v][2]+1});
        dp[u][2] += min({dp[v][0], dp[v][1]+1, dp[v][2]});
    }
    if(col[u] == 1) dp[u][0] = dp[u][2] = 9999999;
    else if(col[u] == 2) dp[u][0] = dp[u][1] = 9999999;
    return; 
}

int calc(){
    dfs(0, 0);
    return *min_element(all(dp[0]));
}

void initialize(int n, vi a, vi b){
    N = n; adj = vvi(n); col = vi(n);
    dp = vvi(n, vi(3));

    for(int x = 0; x < n-1; x++){
        adj[a[x]-1].push_back(b[x]-1);
        adj[b[x]-1].push_back(a[x]-1);
    }
    return;
}

// cat ==> 1
int cat(int v){
    v--; col[v] = 1;
    return calc();
}

// dog ==> 2
int dog(int v){
    v--; col[v] = 2;
    return calc();
}

// neighbor ==> 0
int neighbor(int v){
    v--; col[v] = 0;
    return calc();
}

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