oj.uz

Submission #848192

# Submission time Handle Problem Language Result Execution time Memory
848192 2023-09-11T14:36:55 Z Alora Stranded Far From Home (BOI22_island) C++17
10 / 100
 272 ms 16480 KB 
#include <bits/stdc++.h>
#define name "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define f first
#define se second
#define pii pair<int, ll>
#define getbit(i, j) ((i >> j) & 1)
#define pb push_back
#define all(v) v.begin(), v.end()
#define maxn 200005
const int M = 1e9 + 7;
using namespace std;
mt19937_64 rng(time(0));
int n, m, a[maxn];
vector <int> g[maxn];
priority_queue <pii> q;
bool xd[maxn];

bool check(int x){
    fi(i, 1, n) xd[i] = 0;
    xd[x] = 1;
    ll sum = a[x];
    while(q.size()) q.pop();
    for(auto v: g[x]) xd[v] = 1, q.push({-a[v], v});
    while(q.size()){
        auto [h, u] = q.top(); q.pop();
        if(sum < a[u]) return 0;
        sum += a[u];
        for(auto v: g[u]) if(!xd[v]) xd[v] = 1, q.push({-a[v], v});
    }
    return 1;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
//	freopen(name".inp","r",stdin);
	//freopen(name".out","w",stdout);
    cin >> n >> m;
    fi(i, 1, n) cin >> a[i];
    fi(i, 1, m){
        int u, v; cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }
    if(n <= 2000 && m <= 2000){
        fi(i, 1, n) cout << check(i);
        return 0;
    }
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 143 ms 5196 KB Output is correct
5 Correct 134 ms 5212 KB Output is correct
6 Correct 199 ms 5460 KB Output is correct
7 Correct 139 ms 5212 KB Output is correct
8 Correct 97 ms 5212 KB Output is correct
9 Correct 272 ms 5292 KB Output is correct
10 Correct 55 ms 5212 KB Output is correct
11 Correct 51 ms 5212 KB Output is correct
12 Correct 46 ms 5212 KB Output is correct
13 Correct 91 ms 5256 KB Output is correct
14 Correct 84 ms 5208 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Incorrect 81 ms 16356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Incorrect 64 ms 16480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Incorrect 75 ms 16468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 143 ms 5196 KB Output is correct
5 Correct 134 ms 5212 KB Output is correct
6 Correct 199 ms 5460 KB Output is correct
7 Correct 139 ms 5212 KB Output is correct
8 Correct 97 ms 5212 KB Output is correct
9 Correct 272 ms 5292 KB Output is correct
10 Correct 55 ms 5212 KB Output is correct
11 Correct 51 ms 5212 KB Output is correct
12 Correct 46 ms 5212 KB Output is correct
13 Correct 91 ms 5256 KB Output is correct
14 Correct 84 ms 5208 KB Output is correct
15 Correct 1 ms 4956 KB Output is correct
16 Correct 1 ms 4956 KB Output is correct
17 Incorrect 81 ms 16356 KB Output isn't correct
18 Halted 0 ms 0 KB -