Submission #784770

#	Time	Username	Problem	Language	Result	Execution time	Memory
784770		TheSahib	Stranded Far From Home (BOI22_island)	C++14	100 / 100	556 ms	83908 KiB

island

#include <bits/stdc++.h>

#define ll long long
#define oo 1e9
#define pii pair<int, int>

using namespace std;

const int MAX = 2e5 + 5;

int n, m;
vector<int> g[MAX];
int arr[MAX];

int par[MAX];
set<int> st[MAX];
ll sum[MAX];

int findPar(int node){
    if(par[node] < 0) return node;
    return par[node] = findPar(par[node]);
}

bool unite(int v, int u){
    v = findPar(v);
    u = findPar(u);
    if(v == u) return false;
    if(-par[v] < -par[u]) swap(v, u);
    par[v] += par[u];
    par[u] = v;
    sum[v] += sum[u];
    if(st[v].size() < st[u].size()) swap(st[v], st[u]);
    for(int a:st[u]){
        st[v].insert(a);
    }
    return true;
}

bool same(int v, int u){
    return findPar(v) == findPar(u);
}

map<int, vector<int>> mp;

void solve(){
    memset(par, -1, sizeof(par));
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        mp[arr[i]].push_back(i);
        st[i].insert(i);
        sum[i] = arr[i];
    }
    
    for (int i = 1; i <= m; i++)
    {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bool ans[n + 1];
    memset(ans, 1, sizeof(ans));
    for(auto& p:mp){
        for(int node:p.second){
            for(int to:g[node]){
                if(arr[node] < arr[to]) continue;
                if(sum[findPar(to)] < arr[node] && !same(node, to)){
                    for(int a:st[findPar(to)]){
                        ans[a] = 0;
                    }
                    st[findPar(to)].clear();
                }
                unite(to, node);
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        cout << ans[i];
    }
}

int main()
{
    solve();
}

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