Submission #1290260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290260		nikd	Stranded Far From Home (BOI22_island)	C++17	100 / 100	230 ms	23204 KiB

island

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


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

bool marked;

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

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if(a == b) return;
    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]){
                int k = find(u);
                if(sum[k]<vc[v]) sol[k] = 0;
            }
            merge(u, v);
        }
    }

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

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35