Submission #1129857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129857		ByeWorld	Stranded Far From Home (BOI22_island)	C++20	100 / 100	350 ms	45264 KiB

island

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int MAXA = 1e6;
const int INF = 1e18+10;
const int MOD = 1e9+7;
const int LOG = 32;
const ld EPS = 1e-12;

int n, m, a[MAXN], val[MAXN], par[MAXN];
vector <int> adj[MAXN], vec[MAXN];
vector <pii> edge[MAXN];
int ans[MAXN];

struct dsu {
    int par[MAXN], tot[MAXN];
    void bd(){
        for(int i=1; i<=n+2; i++) par[i] = i, tot[i] = a[i];
    }
    int f(int x){
        return (par[x]==x ? x : par[x]=f(par[x]));
    }
    bool con(int x, int y){
        return f(x) == f(y);
    }
    void mer(int x, int y){
        x = f(x); y = f(y);
        if(x==y) return;
        if(a[x] < a[y]) swap(x, y);
        tot[x] += tot[y]; par[y] = x;
    }
} A, B;
signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    vector <int> cc; cc.pb(-1);
    for(int i=1; i<=n; i++){
        cin >> a[i]; cc.pb(a[i]);
    }
    a[n+1] = INF;
    sort(cc.begin(), cc.end());
    cc.resize(unique(cc.begin(), cc.end()) - cc.begin());

    for(int i=1; i<=n; i++){
        int id = lower_bound(cc.begin(), cc.end(), a[i]) - cc.begin();
        vec[id].pb(i);
    }
    for(int i=1; i<=m; i++){
        int x, y; cin >> x >> y;
        if(a[x] < a[y]) swap(x, y);
        int id = lower_bound(cc.begin(), cc.end(), a[x]) - cc.begin();
        edge[id].pb({x, y}); //x lebih gede
    }
    A.bd(); B.bd();

    for(int i=1; i<cc.size(); i++){
        // cout <<i << ' ' << cc[i] << "cc\n";
        for(auto [x,y] : edge[i]){
            // cout << x << ' '<< y << " xy\n";
            if(a[x] <= A.tot[A.f(y)]) B.mer(x, A.f(y)); //ans sama
        }
        for(auto [x,y] : edge[i]){
            if(a[A.f(y)] == cc[i]){
                B.mer(x, A.f(y));
                // cout << x << ' '<< A.f(y) << " pp\n";
            }
            A.mer(x,y);
        }
        if(i+1 == cc.size()){
            for(auto in : vec[i])
                B.mer(in, n+1);
        }
    }

    for(int i=1; i<=n; i++){
        if(B.f(i) == n+1) ans[i] = 1;
    }
    for(int i=1; i<=n; i++)
        cout << ans[i];
    cout << '\n';
}

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