Submission #1278400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278400		yassia	Stranded Far From Home (BOI22_island)	C++20	0 / 100	308 ms	54292 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];
ll get(ll u) {
    if (u != p[u]){
        p[u] = get(p[u]);
    }
    return p[u];
}
void union_(ll a, ll b){
    a = get(a);
    b = get(b);
    if (a == b) return;
    if (sz[a]<sz[b]){
        swap(a, b);
    }
    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;
        sum[i] = s[i];
    }
    vector<bool> ans(n, true);
    ll k = h.size();
    vector<ll> e;
    for (int j = 0; j < k; j++) {
        auto vc = h[j].second;
        for (ll i: vc) {
            for (auto u: g[i]) {
                if (s[u] <= s[i]) {
                    union_(u, i);
                }
            }
        }

        for (auto J: vc) {
            if (j + 1 < k && sum[get(J)] < h[j + 1].first) {
                //ans[J] = 0;
                e.emplace_back(J);
            }
        }
    }
    set<ll> H;
    for(int q1 = ((int)e.size())-1; q1 >= 0; q1--){
        ll q = e[q1];
        if (ans[q]==0){
            continue;
        }
        ans[q] = 0;
        queue<ll> qu;
        for (auto u : g[q]){
            if (s[q]>=s[u]) qu.push(u);
        }
        while (!qu.empty()){
            auto x = qu.front();
            qu.pop();
            if (ans[x]==0){
                continue;
            }
            ans[x] = 0;
            for (auto u : g[x]){
                if (ans[u]!=0 && s[u]<=s[x]){
                    qu.push(u);
                }
            }
        }
    }
    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