제출 #1275420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275420		tm.khoa.tm	Cats or Dogs (JOI18_catdog)	C++20	컴파일 에러	0 ms	0 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;
//}
//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;
//}

컴파일 시 표준 에러 (stderr) 메시지

catdog.cpp:124:11: error: redefinition of 'const int N'
  124 | const int N = 20;
      |           ^
catdog.cpp:13:11: note: 'const int N' previously defined here
   13 | const int N = 20;
      |           ^
catdog.cpp:125:5: error: redefinition of 'int n'
  125 | int n;
      |     ^
catdog.cpp:14:5: note: 'int n' previously declared here
   14 | int n;
      |     ^
catdog.cpp:126:23: error: redefinition of 'std::vector<std::pair<int, int> > edges'
  126 | vector<pair<int,int>> edges;
      |                       ^~~~~
catdog.cpp:15:23: note: 'std::vector<std::pair<int, int> > edges' previously defined here
   15 | vector<pair<int,int>> edges;
      |                       ^~~~~
catdog.cpp:127:23: error: redefinition of 'std::vector<std::pair<int, int> > adj [20]'
  127 | vector<pair<int,int>> adj[N];
      |                       ^~~
catdog.cpp:16:23: note: 'std::vector<std::pair<int, int> > adj [20]' previously defined here
   16 | vector<pair<int,int>> adj[N];
      |                       ^~~
catdog.cpp:128:5: error: redefinition of 'int pet [20]'
  128 | int pet[N];
      |     ^~~
catdog.cpp:17:5: note: 'int pet [20]' previously declared here
   17 | int pet[N];
      |     ^~~
catdog.cpp:130:6: error: redefinition of 'bool maskSeparates(int)'
  130 | bool maskSeparates(int mask){
      |      ^~~~~~~~~~~~~
catdog.cpp:19:6: note: 'bool maskSeparates(int)' previously defined here
   19 | bool maskSeparates(int mask){
      |      ^~~~~~~~~~~~~
catdog.cpp:158:5: error: redefinition of 'int dangerLevel()'
  158 | int dangerLevel(){
      |     ^~~~~~~~~~~
catdog.cpp:47:5: note: 'int dangerLevel()' previously defined here
   47 | int dangerLevel(){
      |     ^~~~~~~~~~~
catdog.cpp:176:6: error: redefinition of 'void initialize(int, std::vector<int>, std::vector<int>)'
  176 | void initialize(int N, vector<int> A, vector<int> B){
      |      ^~~~~~~~~~
catdog.cpp:65:6: note: 'void initialize(int, std::vector<int>, std::vector<int>)' previously defined here
   65 | void initialize(int N, vector<int> A, vector<int> B){
      |      ^~~~~~~~~~
catdog.cpp:191:5: error: redefinition of 'int cat(int)'
  191 | int cat(int v){
      |     ^~~
catdog.cpp:80:5: note: 'int cat(int)' previously defined here
   80 | int cat(int v){
      |     ^~~
catdog.cpp:196:5: error: redefinition of 'int dog(int)'
  196 | int dog(int v){
      |     ^~~
catdog.cpp:85:5: note: 'int dog(int)' previously defined here
   85 | int dog(int v){
      |     ^~~
catdog.cpp:201:5: error: redefinition of 'int neighbor(int)'
  201 | int neighbor(int v){
      |     ^~~~~~~~
catdog.cpp:90:5: note: 'int neighbor(int)' previously defined here
   90 | int neighbor(int v){
      |     ^~~~~~~~