Submission #1051095

#TimeUsernameProblemLanguageResultExecution timeMemory
1051095sofijavelkovskaStranded Far From Home (BOI22_island)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=2e5, INF=2e9; int n, m; int a[MAXN]; vector<int> adj[MAXN]; int link[MAXN], size[MAXN], cindex[MAXN]; long long sum[MAXN]; set<pair<int, int> > neighbours[MAXN]; bool compare(int x, int y) { return a[x]<a[y]; } int find(int x) { if (x==link[x]) return x; return link[x]=find(link[x]); } void unite(int x, int y, int maxvalue) { x=find(x); y=find(y); if (neighbours[cindex[x]].size()<neighbours[cindex[y]].size()) swap(x, y); for (auto t : neighbours[cindex[y]]) if (t.first>maxvalue) neighbours[cindex[x]].insert(t); neighbours[cindex[y]].clear(); cindex[y]=cindex[x]; if (size[x]<size[y]) swap(x, y); size[x]=size[x]+size[y]; sum[x]=sum[x]+sum[y]; link[y]=x; return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i=0; i<n; i++) cin >> a[i]; for (int i=0; i<m; i++) { int x, y; cin >> x >> y; adj[x-1].push_back(y-1); adj[y-1].push_back(x-1); } int sorted[n]; for (int i=0; i<n; i++) sorted[i]=i; sort(sorted, sorted+n, compare); for (int i=0; i<n; i++) { link[i]=i; size[i]=1; sum[i]=a[i]; cindex[i]=i; for (auto x : adj[i]) neighbours[i].insert({a[x], x}); } map<int, vector<int> > byvalue; for (int i=0; i<n; i++) byvalue[a[i]].push_back(i); bool possible[n]; for (int i=0; i<n; i++) possible[i]=true; queue<int> q; vector<int> todelete[n]; for (auto k : byvalue) { for (auto x : k.second) { for (auto y : adj[x]) if (a[y]<=a[x] && find(x)!=find(y)) unite(x, y, a[x]); } for (auto x : k.second) { int leader=find(x); while (!neighbours[cindex[leader]].empty() && (*neighbours[cindex[leader]].begin()).first<=a[x]) neighbours[cindex[leader]].erase(neighbours[cindex[leader]].begin()); if (neighbours[cindex[leader]].empty()) continue; auto it=neighbours[cindex[leader]].begin(); if (sum[leader]>=(*it).first) { todelete[(*it).second].push_back(x); continue; } possible[x]=false; q.push(x); while (!q.empty()) { int y=q.front(); q.pop(); for (auto t : todelete[y]) if (a[t]<=a[x] && possible[t]) { possible[t]=false; q.push(t); } } } } for (int i=0; i<n; i++) cout << possible[i]; return 0; }

Compilation message (stderr)

island.cpp: In function 'void unite(int, int, int)':
island.cpp:37:9: error: reference to 'size' is ambiguous
   37 |     if (size[x]<size[y])
      |         ^~~~
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 island.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
island.cpp:9:17: note:                 'int size [200000]'
    9 | int link[MAXN], size[MAXN], cindex[MAXN];
      |                 ^~~~
island.cpp:37:17: error: reference to 'size' is ambiguous
   37 |     if (size[x]<size[y])
      |                 ^~~~
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 island.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
island.cpp:9:17: note:                 'int size [200000]'
    9 | int link[MAXN], size[MAXN], cindex[MAXN];
      |                 ^~~~
island.cpp:39:5: error: reference to 'size' is ambiguous
   39 |     size[x]=size[x]+size[y];
      |     ^~~~
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 island.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
island.cpp:9:17: note:                 'int size [200000]'
    9 | int link[MAXN], size[MAXN], cindex[MAXN];
      |                 ^~~~
island.cpp:39:13: error: reference to 'size' is ambiguous
   39 |     size[x]=size[x]+size[y];
      |             ^~~~
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 island.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
island.cpp:9:17: note:                 'int size [200000]'
    9 | int link[MAXN], size[MAXN], cindex[MAXN];
      |                 ^~~~
island.cpp:39:21: error: reference to 'size' is ambiguous
   39 |     size[x]=size[x]+size[y];
      |                     ^~~~
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 island.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
island.cpp:9:17: note:                 'int size [200000]'
    9 | int link[MAXN], size[MAXN], cindex[MAXN];
      |                 ^~~~
island.cpp: In function 'int main()':
island.cpp:68:9: error: reference to 'size' is ambiguous
   68 |         size[i]=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 island.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
island.cpp:9:17: note:                 'int size [200000]'
    9 | int link[MAXN], size[MAXN], cindex[MAXN];
      |                 ^~~~