oj.uz

Submission #993614

# Submission time Handle Problem Language Result Execution time Memory
993614 2024-06-06T08:34:17 Z amine_aroua Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 18304 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];
bool marked[N];
int n , m;
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});
    while(!pq.empty())
    {
        auto [val , node] = pq.top();
        pq.pop();
        if(val > cur)
            break;
        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)
    {
        cout<<1;
    }
    else
    {
        fore(i , n)
        {
            if(vis[i])
                marked[i] = 1;
        }
        cout<<0;
    }
}
signed main()
{
    cin>>n>>m;
    fore(i , n)
        cin>>a[i];
    fore(i , m)
    {
        int u , v;
        cin>>u>>v;
        u-- , v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    fore(i , n)
    {
        if(marked[i])
        {
            cout<<0;
        }
        else
            expand(i);
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 282 ms 6792 KB Output is correct
5 Correct 224 ms 6756 KB Output is correct
6 Correct 369 ms 6744 KB Output is correct
7 Correct 307 ms 6832 KB Output is correct
8 Correct 223 ms 6816 KB Output is correct
9 Correct 5 ms 6744 KB Output is correct
10 Correct 100 ms 6760 KB Output is correct
11 Correct 123 ms 6744 KB Output is correct
12 Correct 88 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 23 ms 6820 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Execution timed out 1094 ms 18304 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 6488 KB Output is correct
2 Execution timed out 1039 ms 12888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 282 ms 6792 KB Output is correct
5 Correct 224 ms 6756 KB Output is correct
6 Correct 369 ms 6744 KB Output is correct
7 Correct 307 ms 6832 KB Output is correct
8 Correct 223 ms 6816 KB Output is correct
9 Correct 5 ms 6744 KB Output is correct
10 Correct 100 ms 6760 KB Output is correct
11 Correct 123 ms 6744 KB Output is correct
12 Correct 88 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 23 ms 6820 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Execution timed out 1094 ms 18304 KB Time limit exceeded
18 Halted 0 ms 0 KB -