Submission #1278449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278449		yassia	Stranded Far From Home (BOI22_island)	C++20	0 / 100	297 ms	81208 KiB

island

#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll,ll>;
using str = string;
using ld = long double;
using hash_map =gp_hash_table<int, int>;
using hash_set= gp_hash_table <int, null_type>;
auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);
typedef tree<ll, null_type, less<>, rb_tree_tag,
        tree_order_statistics_node_update> ord_set;
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const int maxn = 3e5 + 1997;
ll p[maxn];
ll sz[maxn];
ll sum[maxn];

vector<ll> comps[maxn];
ll get(ll u) {
    if (u != p[u]){
        p[u] = get(p[u]);
    }
    return p[u];
}
ll a1[maxn];
vector<bool> ans;
bool used[maxn];
void union_(ll a, ll b){
    a = get(a);
    b = get(b);
    if (a == b) return;
    if (sz[a]<sz[b])swap(a, b);
    for (auto x: comps[b]){
        comps[a].push_back(x);
    }
    comps[b].clear();
    sz[a] += sz[b];
    sum[a] += sum[b];
    p[b] = a;

}
void solve1() {
    ll n, m;
    cin >> n >> m;
    vector<ll> s(n);
    for (int i =0 ; i<n ; i++){
        cin>>s[i];
    }
    map<ll,vector<ll>> f;
    for (int i =0 ; i<n ;i++){
        f[s[i]].push_back(i);
    }
    vector<pair<ll,vector<ll>>> h;
    for (auto &[u, v]:f){
        h.emplace_back(u, v);
    }
    vector<vector<ll>> g(n);
    for (int j = 0; j < m; ++j){
        ll u, v;
        cin>>u>>v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i =0 ; i<n ; i++){
        p[i] = i; sz[i] = 1;
        comps[i] = {i};
        sum[i] = s[i];
        a1[i] = 1;
    }
    ans.resize(n, true);
    ll k = h.size();
    vector<ll> e;
    for (int j = 0; j < k; j++) {
        auto vc = h[j].second;
        for (auto u : vc)used[u] = true;
        for (ll i: vc) {
            for (auto u: g[i]) {
                if (used[u]) {
                    union_(u, i);
                }
            }
        }
        set<ll> j1;
        for (int i : vc){
            j1.insert(get(i));
        }
        for (auto J : j1){
            auto t = get(J);
            if (a1[t]==0)continue;
            if (j + 1 < k && sum[t] < h[j + 1].first) {
                a1[t] = 0;
                for (auto x: comps[t]){
                    ans[x]= 0;
                }
            }
        }
    }
    set<ll> H;

    for (int j = 0; j< n ;j++){
        H.insert(get(j));
    }

    if(H.size()>1){
        for (int j= 0; j<n; j++)cout<<0;
        return;
    }
    for (int s1: ans)cout<<s1;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t1 = 1;
    //cin>>t1;
    for (int o_ = 0; o_ < t1; o_++) {
        solve1();
    }
#ifdef local
    printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC);
#endif
}

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