제출 #1305701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305701		nasir_bashirov	Stranded Far From Home (BOI22_island)	C++20	100 / 100	145 ms	53752 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;
    vector<vi> comp;
    int components;
    DSU(int sz){
        components = sz;
        par.resize(sz + 5, -1);
        w.resize(sz + 5, -1);
        comp.resize(sz + 5);
        for(int i = 1; i <= n; i++) w[i] = b[i], comp[i] = {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;
            for(int i : comp[v]){
                comp[u].push_back(i);
            }
            comp[v].clear();
            components--;
            return true;
        }
        else{
            return false;
        }
    }
};

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);
    }
    sort(a + 1, a + n + 1);
    DSU t(n);
    for(int i = 1; i <= n; i++){
        for(int u : g[a[i].second]){
            // cout << "_ " << i << " " << u << endl;
            if(b[u] > a[i].first)   continue;
            int v = t.Find(u);
            if(t.w[v] < a[i].first){
                for(int j : t.comp[v]){
                    res[j] = 0;
                }
            }
            t.Union(u, a[i].second);
        }  
    }
    for(int i = 1; i <= n; i++) cout << res[i];
    // cout << endl;
}

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

/*
*/

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