Submission #1275420

#TimeUsernameProblemLanguageResultExecution timeMemory
1275420tm.khoa.tmCats or Dogs (JOI18_catdog)C++20
Compilation error
0 ms0 KiB
//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; //}

Compilation message (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){
      |     ^~~~~~~~