제출 #1073053

#제출 시각아이디문제언어결과실행 시간메모리
1073053NeroZein열쇠 (IOI21_keys)C++17
컴파일 에러
0 ms0 KiB
#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; }

컴파일 시 표준 에러 (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) {
      |             ^~~~~~~~~~~~~~