Submission #301897

#	Time	Username	Problem	Language	Result	Execution time	Memory
301897		gevacrt	Cats or Dogs (JOI18_catdog)	C++17	8 / 100	411 ms	384 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;
vvi adj; vi col;

int dfs(int u, int p, int mask){
    int ans = col[u];
    for(auto v : adj[u]){
        if(v == p) continue;
        if(mask&(1<<v)){
            if(dfs(v, u, mask) == 3)
                return 3;
        }else ans |= dfs(v, u, mask);
    }
    return ans;
}

int calc(){
    int ans = INF;
    for(int mask = 0; mask < (1<<N); mask++){
        if(dfs(0, 0, mask) != 3)
            ans = min(ans, __builtin_popcount(mask));
    }
    return ans;
}

void initialize(int n, vi a, vi b){
    N = n; adj = vvi(n); col = vi(n);
    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: 0 / 30
• Subtask 3: 0 / 62