oj.uz

Submission #1006104

# Submission time Handle Problem Language Result Execution time Memory
1006104 2024-06-23T11:57:13 Z nikd Stranded Far From Home (BOI22_island) C++17
25 / 100
 186 ms 36804 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;


vector<bool> sol;
vector<int> p;
vector<int> sum;
vector<vector<int>> adj;
vector<bool> exists;
vector<int> vc;


int find(int a, bool& marked){
    marked &= sol[a];
    if(p[a]==a) return a;
    bool mk = 1;
    p[a] = find(p[a], mk);
    marked &= mk;
    sol[a] = sol[a]&mk;
    return p[a];
}

void merge(int a, int b){
    bool marked = 1; a = find(a, marked);
    marked = 1; b = find(b, marked);
    p[a]=b;
    sum[b] += sum[a];
    return;
}


int32_t main(){
    int n; cin >> n;
    int m; cin >> m;
    vc.resize(n);
    vector<pair<int, int>> vec(n);
    for(int i = 0; i<n; i++){
        int a; cin >> a;
        vc[i] = a;
        vec[i] = {a, i};
    }

    sort(vec.begin(), vec.end());
    sum.resize(n);
    for(int i  =0; i<n; i++) sum[i]=vc[i];

    
    p.resize(n);
    for(int i = 0; i<n; i++) p[i] = i;
    sol.resize(n, 1);
    adj.resize(n);
    exists.resize(n, 0);
        
    for(int i = 0; i<m; i++){
        int a, b;
        cin >> a >> b; a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for(int i = 0; i<n; i++){
        int v = vec[i].second;
        exists[v] = 1;
        for(int u: adj[v]){
            if(!exists[u]) continue;
            if(vc[u]<vc[v]){
                bool marked = 1;
                int k = find(u, marked);
                if(sum[k]<vc[v]) sol[k] = 0;
            }
            merge(u, v);
        }
    }

    for(int i = 0; i<n; i++){
        bool marked = 1;
        find(i, marked);
        cout << sol[i];
    }
    cout << '\n';
    

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 2 ms 604 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 155 ms 20308 KB Output is correct
4 Correct 136 ms 28676 KB Output is correct
5 Correct 148 ms 24028 KB Output is correct
6 Correct 170 ms 24660 KB Output is correct
7 Correct 166 ms 24704 KB Output is correct
8 Correct 180 ms 24696 KB Output is correct
9 Correct 158 ms 25984 KB Output is correct
10 Correct 150 ms 24516 KB Output is correct
11 Correct 174 ms 36804 KB Output is correct
12 Correct 146 ms 23384 KB Output is correct
13 Correct 136 ms 34900 KB Output is correct
14 Correct 140 ms 33620 KB Output is correct
15 Correct 157 ms 23892 KB Output is correct
16 Correct 129 ms 22868 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 158 ms 19280 KB Output is correct
3 Correct 171 ms 23892 KB Output is correct
4 Correct 180 ms 36340 KB Output is correct
5 Correct 135 ms 30772 KB Output is correct
6 Correct 181 ms 23684 KB Output is correct
7 Correct 176 ms 23812 KB Output is correct
8 Correct 180 ms 23932 KB Output is correct
9 Correct 156 ms 23124 KB Output is correct
10 Correct 144 ms 29268 KB Output is correct
11 Correct 143 ms 24660 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 186 ms 20220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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