oj.uz

Submission #993620

# Submission time Handle Problem Language Result Execution time Memory
993620 2024-06-06T08:51:38 Z amine_aroua Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 19136 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 , -1);
void expand(int x)
{
    priority_queue<pair<int ,int> , vector<pair<int ,int>>  , greater<pair<int , int>>> pq;
    int cur = a[x];
    vector<bool> vis(n , 0);
    pq.push({cur , x});
    vector<int> possible;
    while(!pq.empty())
    {
        auto [val , node] = pq.top();
        pq.pop();
        if(val >= cur)
        {
            possible.pb(node);
        }
        if(val > cur)
            continue;
        if(vis[node])
            continue;
        vis[node] = 1;
        if(node != x)
            cur+=val;
        for(auto u : adj[node])
        {
            pq.push({a[u] , u});
        }
    }
    bool acc = 1;
    fore(i , n)
    {
        if(!vis[i])
        {
            acc = 0;
            break;
        }
    }
    if(acc)
    {
        for(auto u : possible)
            ans[u] = 1;
        ans[x] = 1;
    }
    else
    {
        fore(i , n)
        {
            if(vis[i])
                ans[i] = 0;
        }
        ans[x] = 0;
    }
}
signed main()
{
    cin>>n>>m;
    vector<pair<int ,int>> ve;
    fore(i , n)
    {
        cin>>a[i];
        ve.pb({a[i] , i});
    }
    sort(ve.begin() , ve.end());
    fore(i , m)
    {
        int u , v;
        cin>>u>>v;
        u-- , v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(auto [val , i] : ve)
    {
        if(ans[i] == -1)
            expand(i);
    }
    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 276 ms 8028 KB Output is correct
5 Correct 217 ms 8028 KB Output is correct
6 Correct 271 ms 8024 KB Output is correct
7 Correct 288 ms 8024 KB Output is correct
8 Correct 218 ms 8028 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 120 ms 8192 KB Output is correct
11 Correct 115 ms 8192 KB Output is correct
12 Correct 94 ms 8028 KB Output is correct
13 Correct 3 ms 8028 KB Output is correct
14 Correct 23 ms 8224 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Execution timed out 1037 ms 18684 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Execution timed out 1080 ms 18376 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Execution timed out 1091 ms 19136 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 276 ms 8028 KB Output is correct
5 Correct 217 ms 8028 KB Output is correct
6 Correct 271 ms 8024 KB Output is correct
7 Correct 288 ms 8024 KB Output is correct
8 Correct 218 ms 8028 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 120 ms 8192 KB Output is correct
11 Correct 115 ms 8192 KB Output is correct
12 Correct 94 ms 8028 KB Output is correct
13 Correct 3 ms 8028 KB Output is correct
14 Correct 23 ms 8224 KB Output is correct
15 Correct 2 ms 8024 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Execution timed out 1037 ms 18684 KB Time limit exceeded
18 Halted 0 ms 0 KB -