제출 #1275418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275418		tm.khoa.tm	Cats or Dogs (JOI18_catdog)	C++20	8 / 100	18 ms	580 KiB

catdog

//I love ManchesterUnited
#include<bits/stdc++.h>
using namespace std;

#define love ManchesterUnited
#define pb push_back
#define FOR(i,a,b) for (int i=(a); i<=(b); i++)
#define FORD(i,b,a) for (int i=(b); i>=(a); i--)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define endl '\n'

const int N = 20;
int n;
vector<pair<int,int>> edges;
vector<pair<int,int>> adj[N];
int pet[N];

bool maskSeparates(int mask){
    vector<int> vis(n+1,0);
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(pet[i]==1){
            vis[i]=1;
            q.push(i);
        }
    }
    bool anyDog = false, anyCat = false;
    for(int i=1;i<=n;i++){
        if(pet[i]==1) anyCat = true;
        if(pet[i]==2) anyDog = true;
    }
    if(!anyCat || !anyDog) return true;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(auto [v, idx] : adj[u]){
            if(mask & (1<<idx)) continue;
            if(vis[v]) continue;
            if(pet[v]==2) return false;
            vis[v]=1;
            q.push(v);
        }
    }
    return true;
}

int dangerLevel(){
    int m = (int)edges.size();
    bool anyCat = false, anyDog = false;
    for(int i=1;i<=n;i++){
        if(pet[i]==1) anyCat = true;
        if(pet[i]==2) anyDog = true;
    }
    if(!anyCat || !anyDog) return 0;
    for(int k=0;k<=m;k++){
        int limit = 1<<m;
        for(int mask=0; mask<limit; ++mask){
            if(__builtin_popcount(mask) != k) continue;
            if(maskSeparates(mask)) return k;
        }
    }
    return m;
}

void initialize(int N, vector<int> A, vector<int> B){
    n=N;
    edges.clear();
    FOR(i,1,n){ adj[i].clear(); pet[i]=0; }
    for(int i=0;i<n-1;i++){
        int u=A[i], v=B[i];
        edges.pb({u,v});
    }
    for(int i=0;i<(int)edges.size();++i){
        int u = edges[i].first, v = edges[i].second;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
    }
}

int cat(int v){
    pet[v]=1;
    return dangerLevel();
}

int dog(int v){
    pet[v]=2;
    return dangerLevel();
}

int neighbor(int v){
    pet[v]=0;
    return dangerLevel();
}

//int32_t main(){
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    int N;
//    cin >> N;
//    vector<int> A(N-1), B(N-1);
//    for(int i=0;i<N-1;i++) cin >> A[i] >> B[i];
//    initialize(N,A,B);
//    int Q; cin >> Q;
//    while(Q--){
//        int t,v; cin >> t >> v;
//        if(t==1) cout << cat(v) << endl;
//        else if(t==2) cout << dog(v) << endl;
//        else if(t==3) cout << neighbor(v) << endl;
//    }
//    return 0;
//}

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