Submission #1051097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051097		sofijavelkovska	Stranded Far From Home (BOI22_island)	C++17	100 / 100	363 ms	72144 KiB

island

#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], csize[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 (csize[x]<csize[y])
        swap(x, y);
    csize[x]=csize[x]+csize[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;
        csize[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;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35