Submission #857497

#	Time	Username	Problem	Language	Result	Execution time	Memory
857497		Abito	Cats or Dogs (JOI18_catdog)	C++17	8 / 100	165 ms	436 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
const int N=20;
int n,a[N];
bool b[N][N],vis[N];
pair<int,int> e[N];
vector<int> adj[N];
bool dfs(int node){
    if (a[node]==2) return 0;
    vis[node]=true;
    bool ans=true;
    for (auto u:adj[node]){
        if (vis[u] || b[u][node]) continue;
        ans&=dfs(u);
    }return ans;
}
int getans(){
    int ans=n;
    for (int i=0;i<(1<<(n-1));i++){
        int g=__popcount(i);
        for (int j=0;j<n-1;j++) b[e[j].F][e[j].S]=b[e[j].S][e[j].F]=bool(i&(1<<j));
        memset(vis,0,sizeof(vis));
        for (int j=1;j<=n;j++){
            if (a[j]!=1 || vis[j]) continue;
            bool x=dfs(j);
            if (!x) g=n;
        }ans=min(ans,g);
    }return ans;
}
void initialize(int NN, std::vector<int> A, std::vector<int> B) {
    n=NN;
    for (int i=0;i<n-1;i++){
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
        e[i]={A[i],B[i]};
    }return;
}
int cat(int v){
  a[v]=1;
  return getans();
}

int dog(int v) {
  a[v]=2;
  return getans();
}

int neighbor(int v) {
  a[v]=0;
  return getans();
}

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