oj.uz

Submission #1002483

# Submission time Handle Problem Language Result Execution time Memory
1002483 2024-06-19T15:12:10 Z Andrey Stranded Far From Home (BOI22_island) C++14
10 / 100
 113 ms 34660 KB 
#include<bits/stdc++.h>
using namespace std;

vector<long long> haha[200001];
vector<long long> dsu(200001);
vector<long long> tree[200001];
vector<long long> st(200001);
vector<long long> wow(200001);
vector<bool> ans(200001);

long long calc(long long a) {
    long long c = a,e = a;
    while(dsu[c] != c) {
        c = dsu[c];
    }
    while(e != dsu[e]) {
        long long d = dsu[e];
        dsu[e] = c;
        e = d;
    }
    return c;
}

void dfs(long long a) {
    st[a] = wow[a];
    for(long long v: tree[a]) {
        dfs(v);
        st[a]+=st[v];
    }
}

void dude(long long a) {
    ans[a] = true;
    for(long long v: tree[a]) {
        if(st[v] >= wow[a]) {
            dude(v);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,m,a,b,sb = 0;
    cin >> n >> m;
    vector<pair<long long,long long>> wut(0);
    for(long long i = 1; i <= n; i++) {
        cin >> wow[i];
        sb+=wow[i];
    }
    for(int i = 0; i < m; i++) {
        cin >> a >> b;
        if(a > b) {
            swap(a,b);
        }
        tree[a].push_back(b);
    }
 /* sort(wut.begin(),wut.end());
    for(long long i = 0; i < m; i++) {
        cin >> a >> b;
        if(wow[a] > wow[b]) {
            haha[a].push_back(b);
        }
        else {
            haha[b].push_back(a);
        }
    }
    for(long long i = 0; i < wut.size(); i++) {
        long long a = wut[i].second;
        for(long long v: haha[a]) {
            if(calc(v) != calc(a)) {
                tree[a].push_back(calc(v));
                dsu[calc(v)] = a;
            }
        }
    }*/
    dfs(1);
    dude(1);
    for(long long i = 1; i <= n; i++) {
        cout << ans[i];
    }
    cout << endl;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14428 KB Output is correct
2 Correct 5 ms 14444 KB Output is correct
3 Correct 7 ms 14512 KB Output is correct
4 Incorrect 6 ms 14428 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 5 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 81 ms 27348 KB Output is correct
4 Correct 65 ms 25936 KB Output is correct
5 Correct 91 ms 23024 KB Output is correct
6 Correct 81 ms 23204 KB Output is correct
7 Correct 80 ms 23380 KB Output is correct
8 Correct 87 ms 23376 KB Output is correct
9 Correct 87 ms 22096 KB Output is correct
10 Correct 58 ms 19920 KB Output is correct
11 Correct 48 ms 19776 KB Output is correct
12 Correct 61 ms 21840 KB Output is correct
13 Correct 81 ms 33172 KB Output is correct
14 Correct 66 ms 33460 KB Output is correct
15 Correct 113 ms 34640 KB Output is correct
16 Correct 75 ms 33872 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14424 KB Output is correct
2 Incorrect 82 ms 34660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14548 KB Output is correct
2 Incorrect 59 ms 23324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14428 KB Output is correct
2 Correct 5 ms 14444 KB Output is correct
3 Correct 7 ms 14512 KB Output is correct
4 Incorrect 6 ms 14428 KB Output isn't correct
5 Halted 0 ms 0 KB -