제출 #1278318

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278318		yassia	Stranded Far From Home (BOI22_island)	C++20	0 / 100	205 ms	53236 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();
    for (int j = 0; j < k; j++){
        ll wi = h[j].first;
        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;
            }
        }
    }
    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