Submission #1006104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006104		nikd	Stranded Far From Home (BOI22_island)	C++17	25 / 100	186 ms	36804 KiB

island

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