Submission #1084969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084969		dosts	Stranded Far From Home (BOI22_island)	C++17	100 / 100	369 ms	63936 KiB

island

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
#define ordered_set tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>
const int MOD = 1e9+7,inf = 2e18;
const int N = 2e5+50;
 
struct DSU {
    int n;
    vi dad,sz,sm;   
    vector<set<int>> stuff;
    DSU(int nn) {
        n = nn;
        dad.resize(n+1);
        iota(all(dad),0ll);
        sz.assign(n+1,1);
        sm.assign(n+1,1);
        stuff.resize(n+1);
    }
    int find(int x) {
        if (x == dad[x]) return x;
        return find(dad[x]);
    }
    void unite(int x,int y) {
        int a = find(x),b = find(y);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a,b);
        sz[a]+=sz[b];
        dad[b] = a;
        sm[a]+=sm[b];
        for (auto it : stuff[b]) stuff[a].insert(it);
        stuff[b].clear();
    }
    void deletecomp(int x) {
        stuff[find(x)].clear();
    }
};
 
void solve() {
    int n,m;
    cin >> n >> m;
    vi edges[n+1];
    map<int,vi> nds;
    vi w(n+1);
    DSU dsu(n);
    for (int i=1;i<=n;i++) {
        cin >> w[i];
        dsu.sm[i] = w[i];
        nds[w[i]].push_back(i);
    }
    for (int i=1;i<=m;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    for (int i=1;i<=n;i++) dsu.stuff[i].insert(i);
    for (auto& [v,nodes] : nds) {
        for (auto it : nodes) {
            for (auto itt : edges[it]) {
                if (dsu.sm[dsu.find(itt)] < w[it]) dsu.deletecomp(itt);
            }
        }
        for (auto it : nodes) {
            for (auto itt : edges[it]) {
                if (w[itt] <= w[it]) dsu.unite(it,itt);
            }
        }
    }
    for (int i=1;i<=n;i++) cout << dsu.stuff[dsu.find(i)].count(i);
    cout << endl;
}                    
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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