Submission #1051090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051090		sofijavelkovska	Stranded Far From Home (BOI22_island)	C++17	100 / 100	428 ms	76504 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;
}

vector<bool> brute()
{
    vector<bool> possible(n, 0);
    for (int i=0; i<n; i++)
    {
        priority_queue<pair<int, int> > pq;
        pq.push({-a[i], i});
        long long sum=0;
        bool visited[n]={false};
        while (!pq.empty())
        {
            int x=pq.top().second;
            pq.pop();
            if (x!=i && sum<a[x])
                continue;
            if (visited[x])
                continue;
            visited[x]=true;
            sum=sum+a[x];
            for (auto y : adj[x])
                if (!visited[y])
                    pq.push({-a[y], y});
        }
        if (*min_element(visited, visited+n)==1)
            possible[i]=true;
    }

    return possible;
}

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);

    srand(time(0));
    int tc=0;
    int K=10;
    //cin >> tc;
    //while (true)
    {
        /*n=rand()%K+1;
        m=n-1+rand()%K;
        if (m>n*(n-1)/2)
            continue;
        tc=tc+1;
        cout << "tc " << tc << '\n';
        for (int i=0; i<n; i++)
        {
            adj[i].clear();
            neighbours[i].clear();
        }
        for (int i=0; i<n; i++)
            a[i]=rand()%K+1;
        set<pair<int, int> > used;
        for (int x=1; x<n; x++)
        {
            int y=rand()%x;
            adj[x].push_back(y);
            adj[y].push_back(x);
            used.insert({x, y});
        }
        while (used.size()<m)
        {
            int x=rand()%n;
            int y=rand()%n;
            if (x==y)
                continue;
            if (used.count({x, y}) || used.count({y, x}))
                continue;
            adj[x].push_back(y);
            adj[y].push_back(x);
            used.insert({x, y});
        }*/
        /*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].push_back(y);
            adj[y].push_back(x);
        }*/


    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();
        //cout << "x sum min " << x << ' ' << sum[leader] << ' ' << (*it).first << '\n';
        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];

        /*auto br=brute();
        bool flop=false;
        for (int i=0; i<n; i++)
            if (possible[i]!=br[i])
                flop=true;
        if (flop)
        {
            cout << "FLOP\n";
            cout << n << ' ' << m << '\n';
            for (int i=0; i<n; i++)
                cout << a[i] << ' ';
            cout << '\n';
            for (auto edge : used)
                cout << edge.first << ' ' << edge.second << '\n';
            for (int i=0; i<n; i++)
                cout << possible[i];
            cout << '\n';
            for (int i=0; i<n; i++)
                cout << br[i];
            cout << '\n';
            //break;
        }*/
    }

    return 0;
}


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

const int MAXN=2e5, INF=2e9;

int n, m;
int a[MAXN];
vector<int> adj[MAXN];

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);
    }
    set<int> values;
    for (int i=0; i<n; i++)
        values.insert(-a[i]);
    bool possible[n]={false};
    queue<int> q;
    for (auto kt : values)
    {
        int k=-kt;
        bool visited[n]={false};
        for (int i=0; i<n; i++)
        {
            if (a[i]!=k || visited[i])
                continue;
            visited[i]=true;
            long long sum=a[i];
            q.push(i);
            vector<int> nodes;
            nodes.push_back(i);
            int minsum=INF;
            while (!q.empty())
            {
                int x=q.front();
                q.pop();
                for (auto y : adj[x])
                {
                    if (a[y]<=k && !visited[y])
                    {
                        visited[y]=true;
                        sum=sum+a[y];
                        q.push(y);
                        if (a[y]==k)
                            nodes.push_back(y);
                    }
                    if (a[y]>k && possible[y])
                        minsum=min(minsum, a[y]);
                }
            }
            if (minsum>sum && k!=-(*values.begin()))
                continue;
            for (auto x : nodes)
                possible[x]=true;
        }
    }
    for (int i=0; i<n; i++)
        cout << possible[i];

    return 0;
}*/


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

const int MAXN=300000;

int n, m;
int a[MAXN];
vector<int> adj[MAXN];
long long prefix[MAXN];

bool compare(int x, int y)
{
    return a[x]>a[y];
}

long long sum(int l, int r)
{
    if (l==0)
        return prefix[r];

    return prefix[r]-prefix[l-1];
}

vector<bool> brute()
{
    vector<bool> possible(n, 0);
    for (int i=0; i<n; i++)
    {
        priority_queue<pair<int, int> > pq;
        pq.push({-a[i], i});
        long long sum=0;
        bool visited[n]={false};
        while (!pq.empty())
        {
            int x=pq.top().second;
            pq.pop();
            if (x!=i && sum<a[x])
                continue;
            if (visited[x])
                continue;
            visited[x]=true;
            sum=sum+a[x];
            for (auto y : adj[x])
                if (!visited[y])
                    pq.push({-a[y], y});
        }
        if (*min_element(visited, visited+n)==1)
            possible[i]=true;
    }

    return possible;
}

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);

    srand(time(0));
    int tc=0;
    //cin >> tc;
    //while (true)
    {
        tc=tc+1;
        cout << "tc " << tc << '\n';
        n=rand()%100+1, m=0;
        for (int i=0; i<n; i++)
            a[i]=rand()%100000+1;
        //for (int i=0; i<n; i++)
          //  cout << a[i] << ' ';
        //cout << '\n';

    cin >> n >> m;
    for (int i=0; i<n; i++)
        cin >> a[i];
    for (int i=0; i<n; i++)
        adj[i].clear();
    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);
    int possible[n]={false};
    possible[sorted[0]]=true;
    set<int> larger;
    larger.insert(sorted[0]);
    prefix[0]=a[0];
    for (int i=1; i<=n; i++)
        prefix[i]=prefix[i-1]+a[i];
    for (int i=1; i<n; i++)
    {
        int x=sorted[i];
        int l=-1, r=n;
        auto it=larger.lower_bound(x);
        if (it!=larger.end())
            r=*it;
        if (it!=larger.begin())
        {
            it--;
            l=*it;
        }
        if (l!=-1 && possible[l] && sum(l+1, r-1)>=a[l])
            possible[x]=true;
        if (r!=n && possible[r] && sum(l+1, r-1)>=a[r])
            possible[x]=true;
        larger.insert(x);
    }
    for (int i=0; i<n; i++)
        cout << possible[i];

        auto br=brute();
        bool flop=false;
        for (int i=0; i<n; i++)
            if (possible[i]!=br[i])
                flop=true;
        if (flop)
        {
            cout << "FLOP\n";
            cout << n << '\n';
            for (int i=0; i<n; i++)
                cout << a[i] << ' ';
            cout << '\n';
            for (int i=0; i<n; i++)
                cout << possible[i];
            cout << '\n';
            for (int i=0; i<n; i++)
                cout << br[i];
            cout << '\n';
            break;
        }
    }

    return 0;
}*/

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:82:9: warning: unused variable 'tc' [-Wunused-variable]
   82 |     int tc=0;
      |         ^~
island.cpp:83:9: warning: unused variable 'K' [-Wunused-variable]
   83 |     int K=10;
      |         ^

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