Submission #1305563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305563		nasir_bashirov	Stranded Far From Home (BOI22_island)	C++20	0 / 100	1097 ms	22032 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);
        // cout << i << " : ";
        // for(int j : g[i])   cout << j << " ";
        // cout << endl;
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        if(used[a[i].second]) continue;
        DSU t(n);
        // cout << "ai : " << a[i].second << endl;
        queue<int> q;
        q.push(a[i].second);
        while(q.size() > 0){
            int cur = q.front();
            q.pop();
            for(int i : g[cur]){
                int x = t.Find(i), y = t.Find(cur);
                // cout << y << " " << t.w[y] << " " << i << " " << b[i] << endl;
                if(x != y and b[i] <= t.w[y]){
                    t.Union(cur, i);
                    q.push(i);
                }
            }
        }
        // cout << t.components << endl;
        bool f = (t.components == 1 ? true : false);
        q.push(a[i].second);
        res[a[i].second] = f;
        while(q.size() > 0){
            int cur = q.front();
            q.pop();
            used[cur] = true;
            for(int i : g[cur]){
                if(b[i] >= b[cur] and !used[i] and t.Find(cur) == t.Find(i)){
                    res[i] = f;
                    q.push(i);
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) cout << res[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