oj.uz

Submission #1006072

# Submission time Handle Problem Language Result Execution time Memory
1006072 2024-06-23T11:01:38 Z nikd Stranded Far From Home (BOI22_island) C++17
0 / 100
 179 ms 20560 KB 
#include <bits/stdc++.h>
using namespace std;


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

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

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


int 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];

    sz.resize(n, 1);
    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++){
        exists[vec[i].second] = 1;
        int v = vec[i].second;
        for(int u: adj[v]){
            if(!exists[u]) continue;
            if(vc[u]<vc[v]){
                int k = find(u);
                if(sum[k]<vc[v]) sol[k] = 0;
            }
            merge(u, v);
        }
    }

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

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB Output is correct
2 Correct 1 ms 400 KB Output is correct
3 Incorrect 151 ms 20560 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 348 KB Output is correct
2 Incorrect 179 ms 20428 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 348 KB Output is correct
2 Incorrect 178 ms 20544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 -