oj.uz

Submission #646699

# Submission time Handle Problem Language Result Execution time Memory
646699 2022-09-30T12:10:45 Z Tenis0206 Stranded Far From Home (BOI22_island) C++11
10 / 100
 1000 ms 15456 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n,m;
int s[200005];

vector<int> G[200005];

bool sel[200005],reached[200005];

bool check(int nod)
{
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> h;
    for(int i=1;i<=n;i++)
    {
        sel[i] = false;
        reached[i] = false;
    }
    sel[nod] = true;
    reached[nod] = true;
    int nr = s[nod];
    for(auto it : G[nod])
    {
        h.push({s[it],it});
        sel[it] = true;
    }
    for(int i=1;i<n;i++)
    {
        int nod = h.top().second;
        h.pop();
        if(nr < s[nod])
        {
            break;
        }
        reached[nod] = true;
        nr += s[nod];
        for(auto it : G[nod])
        {
            if(sel[it])
            {
                continue;
            }
            h.push({s[it],it});
            sel[it] = true;
        }
    }
    bool ok = true;
    for(int i=1;i<=n;i++)
    {
        ok &= reached[i];
    }
    return ok;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    string s;
    for(int i=1;i<=n;i++)
    {
        s.push_back(check(i) + '0');
    }
    cout<<s<<'\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 148 ms 5076 KB Output is correct
5 Correct 143 ms 5276 KB Output is correct
6 Correct 195 ms 5140 KB Output is correct
7 Correct 161 ms 5152 KB Output is correct
8 Correct 107 ms 5136 KB Output is correct
9 Correct 214 ms 5168 KB Output is correct
10 Correct 63 ms 5036 KB Output is correct
11 Correct 61 ms 5148 KB Output is correct
12 Correct 61 ms 5164 KB Output is correct
13 Correct 108 ms 5116 KB Output is correct
14 Correct 88 ms 5128 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Execution timed out 1092 ms 15456 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 4948 KB Output is correct
2 Execution timed out 1088 ms 13132 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 4948 KB Output is correct
2 Execution timed out 1085 ms 14548 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 148 ms 5076 KB Output is correct
5 Correct 143 ms 5276 KB Output is correct
6 Correct 195 ms 5140 KB Output is correct
7 Correct 161 ms 5152 KB Output is correct
8 Correct 107 ms 5136 KB Output is correct
9 Correct 214 ms 5168 KB Output is correct
10 Correct 63 ms 5036 KB Output is correct
11 Correct 61 ms 5148 KB Output is correct
12 Correct 61 ms 5164 KB Output is correct
13 Correct 108 ms 5116 KB Output is correct
14 Correct 88 ms 5128 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Execution timed out 1092 ms 15456 KB Time limit exceeded
18 Halted 0 ms 0 KB -