Submission #1073053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073053		NeroZein	열쇠 (IOI21_keys)	C++17	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

keys

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int,int> pi;
 
#define MAXN 300000
#define MAXM 300000
#define MAXK 300000
 
// BEGIN UFDS
int par[MAXN + 5], sz[MAXN + 5];
 
void init(){
  for (int i = 0; i < MAXN; ++i){
    par[i] = i;
    sz[i] = 0;
  }
}
 
int findPar(int x){
  if (par[x] != x) par[x] = findPar(par[x]);
  return par[x];
}
 
void merg(int x, int y){ // we can't merge by rank here
  par[findPar(x)] = findPar(y);
}
// END UFDS
 
vector<pi> adjList[MAXN + 5];
vector<int> locked[MAXK + 5];
vector<int> vals;
 
int homekeys[MAXN + 5], vis[MAXN+5], dead[MAXN + 5], last[MAXN + 5];
int keys[MAXK + 5];
int ans;
 
vector<int> reach;
vector<int> haslock;
 
void cleanup(){
  for (auto it : reach) keys[homekeys[it]] = 0;
  for (auto it : haslock) locked[it].clear();
 
  reach.clear();
  haslock.clear();
}
 
void runBFS(int rep, int iter){
  last[rep] = iter;
  queue<int> q;
  q.push(rep);
 
 
  while (!q.empty()){
    int u = q.front();
    q.pop();
 
    if (findPar(u) != rep){
      merg(rep,findPar(u));
      last[findPar(u)] = iter;
      cleanup();
      return;
    }
    if (vis[u]) continue;
    vis[u] = 1;
 
    reach.push_back(u);
    int nk = homekeys[u];
 
    if (keys[nk] == 0){
      keys[nk] = 1;
      while (!locked[nk].empty()){
        q.push(locked[nk].back());
        locked[nk].pop_back();
      }
    }
 
    for (auto it : adjList[u]){
      if (keys[it.second]) q.push(it.first);
      else{
        haslock.push_back(it.second);
        locked[it.second].push_back(it.first);
      }
    }
  }
 
  dead[rep] = 1;
  if ((int) reach.size() < ans){
    vals.clear();
    ans = reach.size();
  }
  if ((int) reach.size() == ans){
    for (auto it : reach) vals.push_back(it);
  }
  cleanup();
}
 
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
  int n = r.size(), m = c.size();
  init();
 
  for (int i = 0; i < n; ++i) homekeys[i] = r[i];
 
  for (int i = 0; i < m; ++i){
    adjList[u[i]].push_back(pi(v[i],c[i]));
    adjList[v[i]].push_back(pi(u[i],c[i]));
  }
 
  ans = n+1;
 
  for (int iter = 1;; ++iter){
    for (int i = 0; i < n; ++i) vis[i] = 0;
    int check = 0;
    for (int i = 0; i < n; ++i){
      if (findPar(i) == i && !dead[i]){
        if (last[i] != iter){
          runBFS(i,iter);
          check = 1;
        }
      }
    }
    if (!check) break;
    assert(iter <= 20);
  }
 
  vector<int> ret(n);
  for(auto it : vals) ret[it] = 1;
 
  return ret;
}
#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int,int> pi;
 
#define MAXN 300000
#define MAXM 300000
#define MAXK 300000
 
// BEGIN UFDS
int par[MAXN + 5], sz[MAXN + 5];
 
void init(){
  for (int i = 0; i < MAXN; ++i){
    par[i] = i;
    sz[i] = 0;
  }
}
 
int findPar(int x){
  if (par[x] != x) par[x] = findPar(par[x]);
  return par[x];
}
 
void merg(int x, int y){ // we can't merge by rank here
  par[findPar(x)] = findPar(y);
}
// END UFDS
 
vector<pi> adjList[MAXN + 5];
vector<int> locked[MAXK + 5];
vector<int> vals;
 
int homekeys[MAXN + 5], vis[MAXN+5], dead[MAXN + 5], last[MAXN + 5];
int keys[MAXK + 5];
int ans;
 
vector<int> reach;
vector<int> haslock;
 
void cleanup(){
  for (auto it : reach) keys[homekeys[it]] = 0;
  for (auto it : haslock) locked[it].clear();
 
  reach.clear();
  haslock.clear();
}
 
void runBFS(int rep, int iter){
  last[rep] = iter;
  queue<int> q;
  q.push(rep);
 
 
  while (!q.empty()){
    int u = q.front();
    q.pop();
 
    if (findPar(u) != rep){
      merg(rep,findPar(u));
      last[findPar(u)] = iter;
      cleanup();
      return;
    }
    if (vis[u]) continue;
    vis[u] = 1;
 
    reach.push_back(u);
    int nk = homekeys[u];
 
    if (keys[nk] == 0){
      keys[nk] = 1;
      while (!locked[nk].empty()){
        q.push(locked[nk].back());
        locked[nk].pop_back();
      }
    }
 
    for (auto it : adjList[u]){
      if (keys[it.second]) q.push(it.first);
      else{
        haslock.push_back(it.second);
        locked[it.second].push_back(it.first);
      }
    }
  }
 
  dead[rep] = 1;
  if ((int) reach.size() < ans){
    vals.clear();
    ans = reach.size();
  }
  if ((int) reach.size() == ans){
    for (auto it : reach) vals.push_back(it);
  }
  cleanup();
}
 
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
  int n = r.size(), m = c.size();
  init();
 
  for (int i = 0; i < n; ++i) homekeys[i] = r[i];
 
  for (int i = 0; i < m; ++i){
    adjList[u[i]].push_back(pi(v[i],c[i]));
    adjList[v[i]].push_back(pi(u[i],c[i]));
  }
 
  ans = n+1;
 
  for (int iter = 1;; ++iter){
    for (int i = 0; i < n; ++i) vis[i] = 0;
    int check = 0;
    for (int i = 0; i < n; ++i){
      if (findPar(i) == i && !dead[i]){
        if (last[i] != iter){
          runBFS(i,iter);
          check = 1;
        }
      }
    }
    if (!check) break;
    assert(iter <= 20);
  }
 
  vector<int> ret(n);
  for(auto it : vals) ret[it] = 1;
 
  return ret;
}

Compilation message (stderr)

keys.cpp:144:5: error: redefinition of 'int par [300005]'
  144 | int par[MAXN + 5], sz[MAXN + 5];
      |     ^~~
keys.cpp:12:5: note: 'int par [300005]' previously declared here
   12 | int par[MAXN + 5], sz[MAXN + 5];
      |     ^~~
keys.cpp:144:20: error: redefinition of 'int sz [300005]'
  144 | int par[MAXN + 5], sz[MAXN + 5];
      |                    ^~
keys.cpp:12:20: note: 'int sz [300005]' previously declared here
   12 | int par[MAXN + 5], sz[MAXN + 5];
      |                    ^~
keys.cpp:146:6: error: redefinition of 'void init()'
  146 | void init(){
      |      ^~~~
keys.cpp:14:6: note: 'void init()' previously defined here
   14 | void init(){
      |      ^~~~
keys.cpp:153:5: error: redefinition of 'int findPar(int)'
  153 | int findPar(int x){
      |     ^~~~~~~
keys.cpp:21:5: note: 'int findPar(int)' previously defined here
   21 | int findPar(int x){
      |     ^~~~~~~
keys.cpp:158:6: error: redefinition of 'void merg(int, int)'
  158 | void merg(int x, int y){ // we can't merge by rank here
      |      ^~~~
keys.cpp:26:6: note: 'void merg(int, int)' previously defined here
   26 | void merg(int x, int y){ // we can't merge by rank here
      |      ^~~~
keys.cpp:163:12: error: redefinition of 'std::vector<std::pair<int, int> > adjList [300005]'
  163 | vector<pi> adjList[MAXN + 5];
      |            ^~~~~~~
keys.cpp:31:12: note: 'std::vector<std::pair<int, int> > adjList [300005]' previously declared here
   31 | vector<pi> adjList[MAXN + 5];
      |            ^~~~~~~
keys.cpp:164:13: error: redefinition of 'std::vector<int> locked [300005]'
  164 | vector<int> locked[MAXK + 5];
      |             ^~~~~~
keys.cpp:32:13: note: 'std::vector<int> locked [300005]' previously declared here
   32 | vector<int> locked[MAXK + 5];
      |             ^~~~~~
keys.cpp:165:13: error: redefinition of 'std::vector<int> vals'
  165 | vector<int> vals;
      |             ^~~~
keys.cpp:33:13: note: 'std::vector<int> vals' previously declared here
   33 | vector<int> vals;
      |             ^~~~
keys.cpp:167:5: error: redefinition of 'int homekeys [300005]'
  167 | int homekeys[MAXN + 5], vis[MAXN+5], dead[MAXN + 5], last[MAXN + 5];
      |     ^~~~~~~~
keys.cpp:35:5: note: 'int homekeys [300005]' previously declared here
   35 | int homekeys[MAXN + 5], vis[MAXN+5], dead[MAXN + 5], last[MAXN + 5];
      |     ^~~~~~~~
keys.cpp:167:25: error: redefinition of 'int vis [300005]'
  167 | int homekeys[MAXN + 5], vis[MAXN+5], dead[MAXN + 5], last[MAXN + 5];
      |                         ^~~
keys.cpp:35:25: note: 'int vis [300005]' previously declared here
   35 | int homekeys[MAXN + 5], vis[MAXN+5], dead[MAXN + 5], last[MAXN + 5];
      |                         ^~~
keys.cpp:167:38: error: redefinition of 'int dead [300005]'
  167 | int homekeys[MAXN + 5], vis[MAXN+5], dead[MAXN + 5], last[MAXN + 5];
      |                                      ^~~~
keys.cpp:35:38: note: 'int dead [300005]' previously declared here
   35 | int homekeys[MAXN + 5], vis[MAXN+5], dead[MAXN + 5], last[MAXN + 5];
      |                                      ^~~~
keys.cpp:167:54: error: redefinition of 'int last [300005]'
  167 | int homekeys[MAXN + 5], vis[MAXN+5], dead[MAXN + 5], last[MAXN + 5];
      |                                                      ^~~~
keys.cpp:35:54: note: 'int last [300005]' previously declared here
   35 | int homekeys[MAXN + 5], vis[MAXN+5], dead[MAXN + 5], last[MAXN + 5];
      |                                                      ^~~~
keys.cpp:168:5: error: redefinition of 'int keys [300005]'
  168 | int keys[MAXK + 5];
      |     ^~~~
keys.cpp:36:5: note: 'int keys [300005]' previously declared here
   36 | int keys[MAXK + 5];
      |     ^~~~
keys.cpp:169:5: error: redefinition of 'int ans'
  169 | int ans;
      |     ^~~
keys.cpp:37:5: note: 'int ans' previously declared here
   37 | int ans;
      |     ^~~
keys.cpp:171:13: error: redefinition of 'std::vector<int> reach'
  171 | vector<int> reach;
      |             ^~~~~
keys.cpp:39:13: note: 'std::vector<int> reach' previously declared here
   39 | vector<int> reach;
      |             ^~~~~
keys.cpp:172:13: error: redefinition of 'std::vector<int> haslock'
  172 | vector<int> haslock;
      |             ^~~~~~~
keys.cpp:40:13: note: 'std::vector<int> haslock' previously declared here
   40 | vector<int> haslock;
      |             ^~~~~~~
keys.cpp:174:6: error: redefinition of 'void cleanup()'
  174 | void cleanup(){
      |      ^~~~~~~
keys.cpp:42:6: note: 'void cleanup()' previously defined here
   42 | void cleanup(){
      |      ^~~~~~~
keys.cpp:182:6: error: redefinition of 'void runBFS(int, int)'
  182 | void runBFS(int rep, int iter){
      |      ^~~~~~
keys.cpp:50:6: note: 'void runBFS(int, int)' previously defined here
   50 | void runBFS(int rep, int iter){
      |      ^~~~~~
keys.cpp:232:13: error: redefinition of 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)'
  232 | vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
      |             ^~~~~~~~~~~~~~
keys.cpp:100:13: note: 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)' previously defined here
  100 | vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
      |             ^~~~~~~~~~~~~~