oj.uz

Submission #654398

# Submission time Handle Problem Language Result Execution time Memory
654398 2022-10-31T08:42:00 Z erto Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 33768 KB 
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define INF (int)(1e9 + 7)
#define INF2 998244353
#define N (ll)(2e5 + 5)
//#define f first
//#define s second
#define int ll
#define lsb(x) (x & (-x))
using namespace std;

int n, m, g, h;
int ans[N], a[N];
vector<int> v[N];
bool used[2005][2005];


void solve(){
    cin >> n >> m;

    for(int i=1; i<=n; i++){
        cin >> a[i];
    }

    for(int i=1; i<=m; i++){
        cin >> g >> h;
        v[g].push_back(h);
        v[h].push_back(g);
    }

    for(int i=1; i<=n; i++){
        int cur = 0, cursz=a[i];
        priority_queue<pair<int, int>> pq;
        pq.push({-a[i], i});

        while(!pq.empty()){
            auto p = pq.top();
            pq.pop();
            int j = p.second;
            if(used[i][j])continue;
            if(cursz < a[j])continue;
            if(j != i)cursz += a[j];

            for(int u : v[j]){
                pq.push({-a[u], u});
            }

            used[i][j] = 1;
            cur++;
            for(int u : v[j]){
                if(!used[i][u]){
                    pq.push({-a[u], u});
                }
            }
        }

        ans[i] = cur == n;
        //cout << cur << ' ';
    }


    for(int i=1; i<=n; i++){
        cout << ans[i];
    }
}   


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    for(int i=1; i<=T; i++){
        solve();
    }
}

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 3 ms 4948 KB Output is correct
4 Correct 567 ms 8372 KB Output is correct
5 Correct 489 ms 9056 KB Output is correct
6 Correct 844 ms 8140 KB Output is correct
7 Correct 575 ms 8364 KB Output is correct
8 Correct 439 ms 7808 KB Output is correct
9 Correct 903 ms 9236 KB Output is correct
10 Correct 296 ms 9036 KB Output is correct
11 Correct 273 ms 9036 KB Output is correct
12 Correct 256 ms 9104 KB Output is correct
13 Correct 515 ms 9124 KB Output is correct
14 Correct 309 ms 9100 KB Output is correct

Subtask #2
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 Execution timed out 1094 ms 24148 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Runtime error 875 ms 33768 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1090 ms 16040 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 3 ms 4948 KB Output is correct
4 Correct 567 ms 8372 KB Output is correct
5 Correct 489 ms 9056 KB Output is correct
6 Correct 844 ms 8140 KB Output is correct
7 Correct 575 ms 8364 KB Output is correct
8 Correct 439 ms 7808 KB Output is correct
9 Correct 903 ms 9236 KB Output is correct
10 Correct 296 ms 9036 KB Output is correct
11 Correct 273 ms 9036 KB Output is correct
12 Correct 256 ms 9104 KB Output is correct
13 Correct 515 ms 9124 KB Output is correct
14 Correct 309 ms 9100 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Execution timed out 1094 ms 24148 KB Time limit exceeded
18 Halted 0 ms 0 KB -