Submission #1006076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006076		nikd	Stranded Far From Home (BOI22_island)	C++17	0 / 100	179 ms	15440 KiB

island

#include <bits/stdc++.h>
using namespace std;


vector<bool> sol;
vector<int> p;

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);
    p[a]=b;
    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];

    
    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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35