oj.uz

Submission #640257

# Submission time Handle Problem Language Result Execution time Memory
640257 2022-09-14T04:50:23 Z christinelynn Stranded Far From Home (BOI22_island) C++17
10 / 100
 128 ms 24988 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll mod=1e9+7;
const ll maxn=2e5+5;
const int INF=1e9+5;
#define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define endl '\n'
int n, m, u, v, arr[maxn], par[maxn];
ll cnt[maxn];
vi adj[maxn];
bool ans[maxn];
void dfs(int now) {
    cnt[now]=arr[now];
    for(auto it : adj[now]) {
        dfs(it);
        cnt[now]+=cnt[it];
    }
}
int main() {
    ok
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> arr[i];
    for(int i=0; i<m; i++) {
        cin >> u >> v;
        adj[min(u, v)].pb(max(u, v));
        par[max(u, v)]=min(u, v);
    }
    dfs(1);
    ans[1]=1;
    cout << 1;
    for(int i=2; i<=n; i++) {
        if(cnt[i]>=arr[par[i]] && ans[par[i]]) {
            ans[i]=1;
        }
        cout << ans[i];
    }
}

Subtask #1
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 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 99 ms 16568 KB Output is correct
4 Correct 102 ms 17256 KB Output is correct
5 Correct 109 ms 13264 KB Output is correct
6 Correct 124 ms 13444 KB Output is correct
7 Correct 128 ms 13432 KB Output is correct
8 Correct 107 ms 13512 KB Output is correct
9 Correct 88 ms 12496 KB Output is correct
10 Correct 65 ms 10228 KB Output is correct
11 Correct 66 ms 10332 KB Output is correct
12 Correct 109 ms 13204 KB Output is correct
13 Correct 110 ms 24852 KB Output is correct
14 Correct 102 ms 24880 KB Output is correct
15 Correct 107 ms 24988 KB Output is correct
16 Correct 75 ms 24776 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4912 KB Output is correct
2 Incorrect 98 ms 24012 KB Output isn't correct
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 Incorrect 88 ms 10700 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 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -