oj.uz

Submission #993757

# Submission time Handle Problem Language Result Execution time Memory
993757 2024-06-06T11:42:13 Z amine_aroua Stranded Far From Home (BOI22_island) C++17
0 / 100
 182 ms 32720 KB 
#include<bits/stdc++.h>
#pragma GCC optmize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define int long long
#define pb push_back
#define fore(i , n) for(int i = 0 ; i<n;i++)
#define forr(i , x , y) for(int i = x ; i <= y; i++)
#define forn(i , x , y) for(int i = x ; i >= y; i--)
const int N = 2e5 + 10;
vector<int> adj[N];
int a[N];
int n , m;
vector<int> ans(N , 0);
vector<bool> vis(N , 0);
int sz[N];
struct DSU
{
    vector<int> e;
    vector<int> sm;
    DSU(int _n)
    {
        e.assign(_n , -1);
        sm.assign(_n , 0);
        fore(i , _n)
            sm[i] = a[i];
    }
    int get(int x)
    {
        return (e[x] < 0 ? x : e[x] = get(e[x]));
    }
    int sz(int x)
    {
        return -e[get(x)];
    }
    int sum(int x)
    {
        return sm[get(x)];
    }
    void unite(int u , int v)
    {
        u = get(u) , v = get(v);
        if(u == v)
            return ;
        if(e[u] > e[v])
            swap(u , v);
        sm[u]+=sm[v];
        e[u]+=e[v];
        e[v] = u;
    }
};
void dfsCompute(int x)
{
    vis[x] = 1;
    for(auto u : adj[x])
    {
        if(vis[u])
            continue;
        if(sz[u] >= a[x])
        {
            ans[u] = 1;
            dfsCompute(u);
        }
    }
}
signed main()
{
    cin>>n>>m;
    vector<pair<int ,int>> order;
    fore(i , n)
    {
        cin>>a[i];
        order.pb({a[i] , i});
    }
    fore(i , m)
    {
        int u , v;
        cin>>u>>v;
        u-- , v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    sort(order.begin() , order.end());
    DSU dsu(n);

    fore(j , n)
    {
        int i = order[j].second;
        for(auto u : adj[i])
        {
            if(a[u] <= a[i])
            {
                dsu.unite(u , i);
            }
        }
        sz[i] = dsu.sum(i);
    }
    ans[order.back().second] = 1;
    dfsCompute(order.back().second);
    fore(i , n)
        cout<<ans[i];
}

Compilation message

island.cpp:2: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    2 | #pragma GCC optmize("O3")
      |

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 167 ms 32720 KB Output is correct
4 Correct 137 ms 25788 KB Output is correct
5 Correct 160 ms 25276 KB Output is correct
6 Incorrect 168 ms 26300 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Incorrect 177 ms 25148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Incorrect 182 ms 26040 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 9560 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Correct 2 ms 9696 KB Output is correct
4 Incorrect 4 ms 9816 KB Output isn't correct
5 Halted 0 ms 0 KB -