제출 #1275393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275393		tm.khoa.tm	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	1 ms	568 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 MAXN = 1005;
int n;
vector<int> adj[MAXN];
int pet[MAXN];

int dangerLevel() {
    vector<int> cats, dogs;
    FOR(i,1,n){
        if (pet[i]==1) cats.pb(i);
        if (pet[i]==2) dogs.pb(i);
    }
    if (cats.empty() || dogs.empty()) return 0;

    int ans = 1e9;
    for (int c : cats){
        queue<int> q;
        vector<int> dist(n+1,-1);
        q.push(c); dist[c]=0;
        while(!q.empty()){
            int u = q.front(); q.pop();
            if (pet[u]==2){
                ans = min(ans, dist[u]);
                break;
            }
            for (int v: adj[u]){
                if (dist[v]==-1){
                    dist[v]=dist[u]+1;
                    q.push(v);
                }
            }
        }
    }
    if (ans==1e9) return 0;
    return ans;
}

void initialize(int N, vector<int> A, vector<int> B){
    n = N;
    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];
        adj[u].pb(v);
        adj[v].pb(u);
    }
}

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();
}

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