Submission #795566

#	Time	Username	Problem	Language	Result	Execution time	Memory
795566		TahirAliyev	Stranded Far From Home (BOI22_island)	C++17	100 / 100	339 ms	36228 KiB

island

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
using namespace std;
 
#define ll long long int
#define oo 4e18
#define pii pair<int, int>

const int MAX = 2e5 + 5;

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

int findset(int u){
    if(par[u] < 0) return u;
    return par[u] = findset(par[u]);
}

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

int arr[MAX];
bool ans[MAX];
vector<int> g[MAX];

int main(){
    memset(par, -1, sizeof(par));
    fill(ans, ans + MAX, 1);
    int n, m; cin >> n >> m;
    vector<pii> v;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        sum[i] = arr[i];
        st[i].push_back(i);
        v.push_back({arr[i], i});
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < m; i++)
    {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(pii node : v){
        for(int to : g[node.second]){
            if(arr[to] > arr[node.second]) continue;
            int pto = findset(to), pnode = findset(node.second);
            if(pto == pnode) continue;
            if(sum[pto] < arr[node.second]){
                for(int a : st[pto]){
                    ans[a] = 0;
                }
                st[pto].clear();
            }
            unite(to, node.second);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i];
    }
    
}

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