oj.uz

Submission #993668

# Submission time Handle Problem Language Result Execution time Memory
993668 2024-06-06T09:47:44 Z amine_aroua Stranded Far From Home (BOI22_island) C++17
35 / 100
 1000 ms 31172 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("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<bool> vis(N , 0);
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];
    pq.push({cur , x});
    vector<int> nodes;
    while(!pq.empty())
    {
        auto [val , node] = pq.top();
        pq.pop();
        if(val > cur)
            break;
        if(vis[node])
            continue;
        vis[node] = 1;
        nodes.pb(node);
        if(node != x)
            cur+=val;
        if(ans[node] == 1)
        {
            ans[x] = 1;
            for(auto v : nodes)
                vis[v] = 0;
            return;
        }
        for(auto u : adj[node])
        {
            pq.push({a[u] , u});
        }
    }
    bool acc = 1;
    if((int)nodes.size() != n)
        acc = 0;
    for(auto u : nodes)
        vis[u] = 0;
    if(acc)
    {
        ans[x] = 1;
    }
    else
    {
        for(auto p : nodes)
        {
            ans[p] = 0;
        }
        ans[x] = 0;
    }
}
signed main()
{

    n = 2e5 , m = n - 1;
    cin>>n>>m;
    vector<pair<int ,int>> ve;
    fore(i , n)
    {

        a[i] = rand()%10;
        cin>>a[i];
        ve.pb({a[i] , i});
    }
    sort(ve.begin() , ve.end());
    fore(i , m)
    {
        int u , v;
        u = i + 1 ;
        v = i + 2;
        cin>>u>>v;
        u-- , v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    int cnt = 0;
    for(auto [val , i] : ve)
    {
        if(ans[i] == -1)
        {
            cnt++;
            expand(i);
        }
    }
    fore(i , n)
    {
        cout<<ans[i];
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 5 ms 6748 KB Output is correct
7 Correct 5 ms 6748 KB Output is correct
8 Correct 4 ms 6804 KB Output is correct
9 Correct 4 ms 6748 KB Output is correct
10 Correct 5 ms 6748 KB Output is correct
11 Correct 5 ms 6748 KB Output is correct
12 Correct 4 ms 6748 KB Output is correct
13 Correct 4 ms 6748 KB Output is correct
14 Correct 12 ms 6852 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 233 ms 22200 KB Output is correct
4 Correct 188 ms 22204 KB Output is correct
5 Correct 484 ms 21688 KB Output is correct
6 Correct 566 ms 22200 KB Output is correct
7 Correct 546 ms 22200 KB Output is correct
8 Correct 259 ms 23480 KB Output is correct
9 Correct 344 ms 23488 KB Output is correct
10 Correct 238 ms 30040 KB Output is correct
11 Correct 229 ms 29236 KB Output is correct
12 Correct 233 ms 25348 KB Output is correct
13 Correct 158 ms 24092 KB Output is correct
14 Correct 174 ms 24248 KB Output is correct
15 Correct 199 ms 25528 KB Output is correct
16 Correct 174 ms 24820 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 375 ms 21072 KB Output is correct
3 Correct 433 ms 21176 KB Output is correct
4 Correct 249 ms 26040 KB Output is correct
5 Correct 168 ms 23736 KB Output is correct
6 Correct 383 ms 21288 KB Output is correct
7 Correct 223 ms 21192 KB Output is correct
8 Correct 230 ms 21148 KB Output is correct
9 Correct 161 ms 20916 KB Output is correct
10 Correct 188 ms 21176 KB Output is correct
11 Correct 229 ms 21176 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 502 ms 22464 KB Output is correct
3 Correct 806 ms 22000 KB Output is correct
4 Correct 615 ms 26556 KB Output is correct
5 Correct 678 ms 26592 KB Output is correct
6 Correct 459 ms 26300 KB Output is correct
7 Execution timed out 1057 ms 31172 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 5 ms 6748 KB Output is correct
7 Correct 5 ms 6748 KB Output is correct
8 Correct 4 ms 6804 KB Output is correct
9 Correct 4 ms 6748 KB Output is correct
10 Correct 5 ms 6748 KB Output is correct
11 Correct 5 ms 6748 KB Output is correct
12 Correct 4 ms 6748 KB Output is correct
13 Correct 4 ms 6748 KB Output is correct
14 Correct 12 ms 6852 KB Output is correct
15 Correct 3 ms 6492 KB Output is correct
16 Correct 3 ms 6492 KB Output is correct
17 Correct 233 ms 22200 KB Output is correct
18 Correct 188 ms 22204 KB Output is correct
19 Correct 484 ms 21688 KB Output is correct
20 Correct 566 ms 22200 KB Output is correct
21 Correct 546 ms 22200 KB Output is correct
22 Correct 259 ms 23480 KB Output is correct
23 Correct 344 ms 23488 KB Output is correct
24 Correct 238 ms 30040 KB Output is correct
25 Correct 229 ms 29236 KB Output is correct
26 Correct 233 ms 25348 KB Output is correct
27 Correct 158 ms 24092 KB Output is correct
28 Correct 174 ms 24248 KB Output is correct
29 Correct 199 ms 25528 KB Output is correct
30 Correct 174 ms 24820 KB Output is correct
31 Correct 3 ms 6488 KB Output is correct
32 Correct 375 ms 21072 KB Output is correct
33 Correct 433 ms 21176 KB Output is correct
34 Correct 249 ms 26040 KB Output is correct
35 Correct 168 ms 23736 KB Output is correct
36 Correct 383 ms 21288 KB Output is correct
37 Correct 223 ms 21192 KB Output is correct
38 Correct 230 ms 21148 KB Output is correct
39 Correct 161 ms 20916 KB Output is correct
40 Correct 188 ms 21176 KB Output is correct
41 Correct 229 ms 21176 KB Output is correct
42 Correct 3 ms 6492 KB Output is correct
43 Correct 502 ms 22464 KB Output is correct
44 Correct 806 ms 22000 KB Output is correct
45 Correct 615 ms 26556 KB Output is correct
46 Correct 678 ms 26592 KB Output is correct
47 Correct 459 ms 26300 KB Output is correct
48 Execution timed out 1057 ms 31172 KB Time limit exceeded
49 Halted 0 ms 0 KB -