oj.uz

Submission #1050859

# Submission time Handle Problem Language Result Execution time Memory
1050859 2024-08-09T15:42:21 Z sofijavelkovska Stranded Far From Home (BOI22_island) C++17
10 / 100
 225 ms 58960 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=300000;
// 2e5 ??

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 (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 (csize[x]<csize[y])
        swap(x, y);
    csize[x]=csize[x]+csize[y];
    sum[x]=sum[x]+sum[y];
    link[y]=x;
    if (neighbours[cindex[x]].size()<neighbours[cindex[y]].size())
    {
        for (auto t : neighbours[cindex[x]])
            neighbours[cindex[y]].insert(t);
        neighbours[cindex[y]].erase({a[xt], xt});
        neighbours[cindex[y]].erase({a[yt], yt});
        neighbours[cindex[x]].clear();
        cindex[x]=cindex[y];
    }
    else
    {
        for (auto t : neighbours[cindex[y]])
            neighbours[cindex[x]].insert(t);
        neighbours[cindex[x]].erase({a[xt], xt});
        neighbours[cindex[x]].erase({a[yt], yt});
        neighbours[cindex[y]].clear();
        cindex[y]=cindex[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];
        for (auto x : adj[i])
            neighbours[i].insert({a[x], x});
        cindex[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[cindex[leader]].empty())
            continue;
        auto it=neighbours[cindex[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;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27228 KB Output is correct
2 Correct 3 ms 27228 KB Output is correct
3 Correct 3 ms 27228 KB Output is correct
4 Incorrect 4 ms 27760 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 3 ms 27228 KB Output is correct
2 Correct 3 ms 27228 KB Output is correct
3 Correct 104 ms 58704 KB Output is correct
4 Correct 115 ms 57424 KB Output is correct
5 Correct 126 ms 57680 KB Output is correct
6 Correct 132 ms 58800 KB Output is correct
7 Correct 119 ms 58704 KB Output is correct
8 Correct 163 ms 58708 KB Output is correct
9 Correct 101 ms 58552 KB Output is correct
10 Correct 225 ms 58728 KB Output is correct
11 Correct 152 ms 58564 KB Output is correct
12 Correct 152 ms 57476 KB Output is correct
13 Correct 98 ms 57172 KB Output is correct
14 Correct 116 ms 57344 KB Output is correct
15 Correct 93 ms 58704 KB Output is correct
16 Correct 73 ms 57696 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27228 KB Output is correct
2 Incorrect 160 ms 58960 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 27224 KB Output is correct
2 Incorrect 180 ms 58796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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