oj.uz

Submission #993619

# Submission time Handle Problem Language Result Execution time Memory
993619 2024-06-06T08:50:24 Z amine_aroua Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 22744 KB 
#include<bits/stdc++.h>
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.rbegin() , ve.rend());
    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];
}

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 277 ms 8028 KB Output is correct
5 Correct 226 ms 8200 KB Output is correct
6 Correct 245 ms 8028 KB Output is correct
7 Correct 291 ms 8028 KB Output is correct
8 Correct 221 ms 8024 KB Output is correct
9 Correct 4 ms 8280 KB Output is correct
10 Correct 121 ms 8024 KB Output is correct
11 Correct 121 ms 8276 KB Output is correct
12 Correct 94 ms 8028 KB Output is correct
13 Correct 4 ms 8028 KB Output is correct
14 Correct 23 ms 8028 KB Output is correct

Subtask #2
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 Execution timed out 1092 ms 22744 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 1096 ms 17552 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 19056 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 277 ms 8028 KB Output is correct
5 Correct 226 ms 8200 KB Output is correct
6 Correct 245 ms 8028 KB Output is correct
7 Correct 291 ms 8028 KB Output is correct
8 Correct 221 ms 8024 KB Output is correct
9 Correct 4 ms 8280 KB Output is correct
10 Correct 121 ms 8024 KB Output is correct
11 Correct 121 ms 8276 KB Output is correct
12 Correct 94 ms 8028 KB Output is correct
13 Correct 4 ms 8028 KB Output is correct
14 Correct 23 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Execution timed out 1092 ms 22744 KB Time limit exceeded
18 Halted 0 ms 0 KB -