제출 #1053119

#제출 시각아이디문제언어결과실행 시간메모리
1053119epicci23열쇠 (IOI21_keys)C++17
컴파일 에러
0 ms0 KiB
#include "bits/stdc++.h" //#define int long long #define all(v) v.begin() , v.end() #define sz(a) (int)a.size() using namespace std; const int N = 3e5 + 5; struct DSU{ vector<int> par,sub; DSU(int g){ par.assign(g+5,0); sub.assign(g+5,1); iota(all(par),0); } int find(int a){ if(par[a]==a) return a; return par[a]=find(par[a]); } bool merge(int a,int b){ a=find(a),b=find(b); if(a==b) return 0; if(sub[a]>sub[b]) swap(a,b); sub[b]+=sub[a]; par[a]=b; return 1; } }; DSU dsu(N); int n,m; bitset<30> col[N]; vector<array<int,3>> edges; vector<int> v[N],v2[N]; vector<int> vis,topo,scc; void build(){ for(int i=0;i<n;i++) v[i].clear(),v2[i].clear(); for(auto x:edges){ if(col[x[0]][x[2]]){ //cout << "edge: " << x[0] << ' ' << x[1] << '\n'; v[x[0]].push_back(x[1]); v2[x[1]].push_back(x[0]); } if(col[x[1]][x[2]]){ //cout << "edge: " << x[1] << ' ' << x[0] << '\n'; v[x[1]].push_back(x[0]); v2[x[0]].push_back(x[1]); } } } void dfs(int c,int t){ if(vis[c] || dsu.find(c)!=c) return; vis[c]=1; if(t){ for(int x:v[c]) dfs(x,t); topo.push_back(c); } else{ for(int x:v2[c]) dfs(x,t); scc.push_back(c); } } vector<vector<int>> find_scc(){ topo.clear(); vis.assign(n+5,0); for(int i=0;i<n;i++) dfs(i,1); vector<vector<int>> res; vis.assign(n+5,0); reverse(all(topo)); for(int x:topo){ if(vis[x]) continue; scc.clear(); dfs(x,0); res.push_back(scc); } return res; } vector<int> find_reachable(vector<int> r, vector<int> git, vector<int> gel, vector<int> renk) { vector<int> ans(sz(r),-1); n=sz(r),m=sz(git); for(int i=0;i<n;i++) col[i][r[i]]=1; for(int i=0;i<m;i++){ int a=git[i],b=gel[i],c=renk[i]; edges.push_back({a,b,c}); } while(1){ build(); auto res=find_scc(); bool ok=1; for(vector<int> x:res) if(sz(x)>1) ok=0; if(ok) break; for(vector<int> x:res){ if(sz(x)==1) continue; int p=sz(x); for(int i=0;i<p-1;i++){ if(!dsu.merge(x[i],x.back())) continue; //if(sz(col[x[i]])>sz(col[x.back()])) swap(x[i],x[p-1]); for(int u:col[x[i]]) col[x[p-1]][u]=1; } if(dsu.find(x[p-1])!=x[p-1]) swap(col[x[p-1]],col[dsu.find(x[p-1])]); } vector<array<int,3>> new_edges; for(auto x:edges){ if(dsu.find(x[0])==dsu.find(x[1])) continue; new_edges.push_back({dsu.find(x[0]),dsu.find(x[1]),x[2]}); } edges=new_edges; } int mini=(int)1e9+5; for(int i=0;i<n;i++){ if(!v[dsu.find(i)].empty()){ ans[i]=0; continue; } mini=min(mini,dsu.sub[dsu.find(i)]); } for(int i=0;i<n;i++){ if(ans[i]!=-1) continue; if(mini==dsu.sub[dsu.find(i)]) ans[i]=1; else ans[i]=0; } return ans; } /*void _(){ cin >> n >> m; for(int i=1;i<=n;i++){ int a;cin >> a; col[i].insert(a); } for(int i=1;i<=m;i++){ int a,b,c; cin >> a >> b >> c; edges.push_back({a,b,c}); } while(1){ build(); auto res=find_scc(); bool ok=1; for(vector<int> x:res) if(sz(x)>1) ok=0; if(ok) break; for(vector<int> x:res){ if(sz(x)==1) continue; int p=sz(x); for(int i=0;i<p-1;i++){ if(!dsu.merge(x[i],x.back())) continue; if(sz(col[x[i]])>sz(col[x.back()])) swap(x[i],x[p-1]); for(int u:col[x[i]]) col[x[p-1]].insert(u); } if(dsu.find(x[p-1])!=x[p-1]) swap(col[x[p-1]],col[dsu.find(x[p-1])]); } vector<array<int,3>> new_edges; for(auto x:edges){ if(dsu.find(x[0])==dsu.find(x[1])) continue; new_edges.push_back({dsu.find(x[0]),dsu.find(x[1]),x[2]}); } edges=new_edges; } vector<int> ans(n+5,-1); int mini=(int)1e9+5; for(int i=1;i<=n;i++){ if(!v[dsu.find(i)].empty()){ ans[i]=0; continue; } mini=min(mini,dsu.sub[dsu.find(i)]); } for(int i=1;i<=n;i++){ if(ans[i]!=-1) continue; if(mini==dsu.sub[dsu.find(i)]) ans[i]=1; else ans[i]=0; } for(int i=1;i<=n;i++) cout << ans[i] << " \n"[i==n]; } int32_t main(){ cin.tie(0); ios::sync_with_stdio(0); int tc=1;//cin >> tc; while(tc--) _(); return 0; }*/

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

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:103:27: error: no matching function for call to 'begin(std::bitset<30>&)'
  103 |         for(int u:col[x[i]]) col[x[p-1]][u]=1;
      |                           ^
In file included from /usr/include/c++/10/bits/range_access.h:36,
                 from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from keys.cpp:1:
/usr/include/c++/10/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
   90 |     begin(initializer_list<_Tp> __ils) noexcept
      |     ^~~~~
/usr/include/c++/10/initializer_list:90:5: note:   template argument deduction/substitution failed:
keys.cpp:103:27: note:   'std::bitset<30>' is not derived from 'std::initializer_list<_Tp>'
  103 |         for(int u:col[x[i]]) col[x[p-1]][u]=1;
      |                           ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from keys.cpp:1:
/usr/include/c++/10/bits/range_access.h:51:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&)'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:51:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&) [with _Container = std::bitset<30>]':
keys.cpp:103:27:   required from here
/usr/include/c++/10/bits/range_access.h:51:50: error: 'class std::bitset<30>' has no member named 'begin'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |                                           ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&)'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&) [with _Container = std::bitset<30>]':
keys.cpp:103:27:   required from here
/usr/include/c++/10/bits/range_access.h:61:56: error: 'const class std::bitset<30>' has no member named 'begin'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |                                                 ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
   90 |     begin(_Tp (&__arr)[_Nm])
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note:   template argument deduction/substitution failed:
keys.cpp:103:27: note:   mismatched types '_Tp [_Nm]' and 'std::bitset<30>'
  103 |         for(int u:col[x[i]]) col[x[p-1]][u]=1;
      |                           ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from keys.cpp:1:
/usr/include/c++/10/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
 1214 |     begin(valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1214:5: note:   template argument deduction/substitution failed:
keys.cpp:103:27: note:   'std::bitset<30>' is not derived from 'std::valarray<_Tp>'
  103 |         for(int u:col[x[i]]) col[x[p-1]][u]=1;
      |                           ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from keys.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1224:5: note:   template argument deduction/substitution failed:
keys.cpp:103:27: note:   'std::bitset<30>' is not derived from 'const std::valarray<_Tp>'
  103 |         for(int u:col[x[i]]) col[x[p-1]][u]=1;
      |                           ^
keys.cpp:103:27: error: no matching function for call to 'end(std::bitset<30>&)'
In file included from /usr/include/c++/10/bits/range_access.h:36,
                 from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from keys.cpp:1:
/usr/include/c++/10/initializer_list:101:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
  101 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
/usr/include/c++/10/initializer_list:101:5: note:   template argument deduction/substitution failed:
keys.cpp:103:27: note:   'std::bitset<30>' is not derived from 'std::initializer_list<_Tp>'
  103 |         for(int u:col[x[i]]) col[x[p-1]][u]=1;
      |                           ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from keys.cpp:1:
/usr/include/c++/10/bits/range_access.h:71:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
   71 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:71:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&) [with _Container = std::bitset<30>]':
keys.cpp:103:27:   required from here
/usr/include/c++/10/bits/range_access.h:71:48: error: 'class std::bitset<30>' has no member named 'end'
   71 |     end(_Container& __cont) -> decltype(__cont.end())
      |                                         ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:81:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
   81 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:81:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&) [with _Container = std::bitset<30>]':
keys.cpp:103:27:   required from here
/usr/include/c++/10/bits/range_access.h:81:54: error: 'const class std::bitset<30>' has no member named 'end'
   81 |     end(const _Container& __cont) -> decltype(__cont.end())
      |                                               ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:100:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
  100 |     end(_Tp (&__arr)[_Nm])
      |     ^~~
/usr/include/c++/10/bits/range_access.h:100:5: note:   template argument deduction/substitution failed:
keys.cpp:103:27: note:   mismatched types '_Tp [_Nm]' and 'std::bitset<30>'
  103 |         for(int u:col[x[i]]) col[x[p-1]][u]=1;
      |                           ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from keys.cpp:1:
/usr/include/c++/10/valarray:1234:5: note: candidate: 'template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)'
 1234 |     end(valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/10/valarray:1234:5: note:   template argument deduction/substitution failed:
keys.cpp:103:27: note:   'std::bitset<30>' is not derived from 'std::valarray<_Tp>'
  103 |         for(int u:col[x[i]]) col[x[p-1]][u]=1;
      |                           ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from keys.cpp:1:
/usr/include/c++/10/valarray:1244:5: note: candidate: 'template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/10/valarray:1244:5: note:   template argument deduction/substitution failed:
keys.cpp:103:27: note:   'std::bitset<30>' is not derived from 'const std::valarray<_Tp>'
  103 |         for(int u:col[x[i]]) col[x[p-1]][u]=1;
      |                           ^