Submission #1305694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305694		nasir_bashirov	Stranded Far From Home (BOI22_island)	C++20	0 / 100	104 ms	21852 KiB

island

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define int ll

const int sz = 2e5 + 5;
int n, m, x, y, res[sz], b[sz];
pii a[sz];
bool used[sz];
vi g[sz], tmp;

struct DSU{
    vi par, w;
    int components;
    DSU(int sz){
        components = sz;
        par.resize(sz + 5, -1);
        w.resize(sz + 5, -1);
        for(int i = 1; i <= n; i++) w[i] = b[i];
    }
    int Find(int u){
        if(par[u] < 0)   return u;
        else    return par[u] = Find(par[u]);
    }
    bool Union(int u, int v){
        u = Find(u), v = Find(v);
        if(u != v){
            if(par[u] > par[v]){
                swap(u, v);
            }
            par[u] += par[v], w[u] += w[v];
            par[v] = u;
            components--;
            return true;
        }
        else{
            return false;
        }
    }
};

bool comp(int x, int y){
    return b[x] <= b[y];
}

void fmain(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i].first;
        b[i] = a[i].first;
        res[i] = 1;
        a[i].second = i;
    }
    while(m--){
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 1; i <= n; i++){
        sort(all(g[i]), comp);
    }
    sort(a + 1, a + n + 1);
    queue<int> q;
    DSU t(n);
    set<int> par;
    for(int i = 1; i <= n; i++){
        for(int u : g[a[i].second]){
            if(b[u] > a[i].first)   continue;
            int v = t.Find(u);
            if(t.w[v] < a[i].first){
                res[v] = 0;
            }
            else{
                t.Union(u, a[i].second);
            }
        }  
    }
    for(int i = 1; i <= n; i++) cout << res[t.Find(i)];
    // cout << endl;
}

signed main(){
    fastio;
    int _ = 1;  
    // cin >> _;    
    while(_--){
        fmain();
    }
}

/*
*/

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