Submission #640387

#	Time	Username	Problem	Language	Result	Execution time	Memory
640387		christinelynn	Stranded Far From Home (BOI22_island)	C++17	0 / 100	237 ms	30776 KiB

island

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define ll long long
#define ld long double

struct DSU{
    vector<vector<int>> group;
    vector<int> par;
    vector<ll> sz, val;
    int N;

    DSU(int _N){
        N = _N;
        sz = vector<ll>(N+1);
        val = vector<ll>(N+1);
        par = vector<int>(N+1); iota(par.begin(), par.end(), 0);
        group = vector<vector<int>>(N+1); for(int i = 1; i <= N; ++i)group[i].push_back(i);
    }

    int rep(int x){
        if(par[x] == x)return x;
        return par[x] = rep(par[x]);
    }

    void comb(int u, int v){
        int pu = rep(u), pv = rep(v);
        if(pu != pv){
            if(val[pv] < sz[u]){
                vector<int>().swap(group[v]);
            }
            if((int)group[pu].size() > (int)group[pv].size()){
                swap(pu, pv);
            }
            for(int elem : group[pu]){
                group[pv].push_back(elem);
            }
            vector<int>().swap(group[pu]);
            val[pv] += val[pu];
            par[pu] = pv;
        }
    }
};

vector<int> adj[200005];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, M; cin >> N >> M;

    DSU dsu(N);

    vector<pair<int, int>> order;
    for(int i = 1; i <= N; ++i){
        int x; cin >> x;
        dsu.val[i] = dsu.sz[i] = x;
        order.push_back({x, i});
    }

    for(int i = 1; i <= M; ++i){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    sort(order.begin(), order.end());

    vector<bool> vis(N+1);
    for(int i = 0; i < N; ++i){
        int cur = order[i].second;
        vis[cur] = 1;
        for(int nx : adj[cur]){
            if(vis[nx]){
                dsu.comb(cur, nx);
            }
        }
    }

    vector<bool> answer(N+1);
    for(int elem : dsu.group[dsu.rep(1)]){
        answer[elem] = 1;
    }

    for(int i = 1; i <= N; ++i){
        cout << answer[i];
    }

    return 0;
}

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