Submission #1050855

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1050855	2024-08-09T15:40:01 Z	sofijavelkovska	Stranded Far From Home (BOI22_island)	C++17	Compilation error	0 ms	0 KB

island

#include <bits/stdc++.h>
using namespace std;

const int MAXN=300000;

int n, m;
int a[MAXN];
vector<int> adj[MAXN];
int link[MAXN], size[MAXN], index[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 (link[x]==x)
        return x;

    return link[x]=find(link[x]);
}

void unite(int x, int y)
{
    int xt=x, yt=y;
    x=find(x);
    y=find(y);
    if (size[x]<size[y])
        swap(x, y);
    size[x]=size[x]+size[y];
    sum[x]=sum[x]+sum[y];
    link[y]=x;
    if (neighbours[index[x]].size()<neighbours[index[y]].size())
    {
        for (auto t : neighbours[index[x]])
            neighbours[index[y]].insert(t);
        neighbours[index[y]].erase({a[xt], xt});
        neighbours[index[y]].erase({a[yt], yt});
        neighbours[index[x]].clear();
        index[x]=index[y];
    }
    else
    {
        for (auto t : neighbours[index[y]])
            neighbours[index[x]].insert(t);
        neighbours[index[x]].erase({a[xt], xt});
        neighbours[index[x]].erase({a[yt], yt});
        neighbours[index[y]].clear();
        index[y]=index[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];
        for (auto x : adj[i])
            neighbours[i].insert({a[x], x});
        index[i]=i;

    }
    bool possible[n];
    for (int i=0; i<n; i++)
        possible[i]=true;
    queue<int> q;
    for (int i=0; i<n; i++)
    {
        int x=sorted[i];
        for (auto y : adj[x])
            if (a[y]<=a[x] && find(x)!=find(y))
                unite(x, y);
        int leader=find(x);
        if (neighbours[index[leader]].empty())
            continue;
        auto it=neighbours[index[leader]].begin();
        //cout << "x " << x << '\n';
        //cout << "sum max " << sum[leader] << ' ' << (*it).first << '\n';
        if (sum[leader]>=(*it).first)
            continue;
        possible[x]=false;
        q.push(x);
        while (!q.empty())
        {
            int y=q.front();
            q.pop();
            for (auto t : adj[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

island.cpp:9:39: error: 'int index [300000]' redeclared as different kind of entity
    9 | int link[MAXN], size[MAXN], index[MAXN];
      |                                       ^
In file included from /usr/include/string.h:432,
                 from /usr/include/c++/10/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
                 from island.cpp:1:
/usr/include/strings.h:61:1: note: previous declaration 'const char* index(const char*, int)'
   61 | index (const char *__s, int __c) __THROW
      | ^~~~~
island.cpp: In function 'void unite(int, int)':
island.cpp:31:9: error: reference to 'size' is ambiguous
   31 |     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 [300000]'
    9 | int link[MAXN], size[MAXN], index[MAXN];
      |                 ^~~~
island.cpp:31:17: error: reference to 'size' is ambiguous
   31 |     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 [300000]'
    9 | int link[MAXN], size[MAXN], index[MAXN];
      |                 ^~~~
island.cpp:33:5: error: reference to 'size' is ambiguous
   33 |     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 [300000]'
    9 | int link[MAXN], size[MAXN], index[MAXN];
      |                 ^~~~
island.cpp:33:13: error: reference to 'size' is ambiguous
   33 |     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 [300000]'
    9 | int link[MAXN], size[MAXN], index[MAXN];
      |                 ^~~~
island.cpp:33:21: error: reference to 'size' is ambiguous
   33 |     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 [300000]'
    9 | int link[MAXN], size[MAXN], index[MAXN];
      |                 ^~~~
island.cpp:36:25: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   36 |     if (neighbours[index[x]].size()<neighbours[index[y]].size())
      |                         ^
island.cpp:36:53: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   36 |     if (neighbours[index[x]].size()<neighbours[index[y]].size())
      |                                                     ^
island.cpp:38:39: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   38 |         for (auto t : neighbours[index[x]])
      |                                       ^
island.cpp:39:29: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   39 |             neighbours[index[y]].insert(t);
      |                             ^
island.cpp:40:25: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   40 |         neighbours[index[y]].erase({a[xt], xt});
      |                         ^
island.cpp:41:25: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   41 |         neighbours[index[y]].erase({a[yt], yt});
      |                         ^
island.cpp:42:25: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   42 |         neighbours[index[x]].clear();
      |                         ^
island.cpp:43:14: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   43 |         index[x]=index[y];
      |              ^
island.cpp:43:23: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   43 |         index[x]=index[y];
      |                       ^
island.cpp:47:39: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   47 |         for (auto t : neighbours[index[y]])
      |                                       ^
island.cpp:48:29: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   48 |             neighbours[index[x]].insert(t);
      |                             ^
island.cpp:49:25: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   49 |         neighbours[index[x]].erase({a[xt], xt});
      |                         ^
island.cpp:50:25: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   50 |         neighbours[index[x]].erase({a[yt], yt});
      |                         ^
island.cpp:51:25: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   51 |         neighbours[index[y]].clear();
      |                         ^
island.cpp:52:14: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   52 |         index[y]=index[x];
      |              ^
island.cpp:52:23: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   52 |         index[y]=index[x];
      |                       ^
island.cpp: In function 'int main()':
island.cpp:80:9: error: reference to 'size' is ambiguous
   80 |         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 [300000]'
    9 | int link[MAXN], size[MAXN], index[MAXN];
      |                 ^~~~
island.cpp:84:14: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   84 |         index[i]=i;
      |              ^
island.cpp:98:29: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   98 |         if (neighbours[index[leader]].empty())
      |                             ^
island.cpp:100:33: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
  100 |         auto it=neighbours[index[leader]].begin();
      |                                 ^