oj.uz

Submission #1051070

# Submission time Handle Problem Language Result Execution time Memory
1051070 2024-08-09T19:14:10 Z sofijavelkovska Stranded Far From Home (BOI22_island) C++17
10 / 100
 392 ms 71636 KB 
#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;
    //cin >> tc;
    //while (true)
    {
        /*n=rand()%5+1;
        m=n-1+rand()%5;
        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()%5+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-1].push_back(y-1);
            adj[y-1].push_back(x-1);
        }


    /*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;
    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)
            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];

        /*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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19292 KB Output is correct
3 Correct 3 ms 19040 KB Output is correct
4 Incorrect 4 ms 19292 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 19032 KB Output is correct
3 Correct 226 ms 71636 KB Output is correct
4 Correct 147 ms 49932 KB Output is correct
5 Correct 274 ms 69972 KB Output is correct
6 Correct 229 ms 66384 KB Output is correct
7 Correct 248 ms 71572 KB Output is correct
8 Correct 252 ms 51144 KB Output is correct
9 Correct 216 ms 66484 KB Output is correct
10 Correct 266 ms 66496 KB Output is correct
11 Correct 276 ms 50968 KB Output is correct
12 Correct 204 ms 49820 KB Output is correct
13 Correct 138 ms 49604 KB Output is correct
14 Correct 147 ms 49920 KB Output is correct
15 Correct 194 ms 71540 KB Output is correct
16 Correct 162 ms 70460 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Incorrect 392 ms 71272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 292 ms 50928 KB Output is correct
3 Incorrect 255 ms 50792 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19292 KB Output is correct
3 Correct 3 ms 19040 KB Output is correct
4 Incorrect 4 ms 19292 KB Output isn't correct
5 Halted 0 ms 0 KB -