Submission #1109540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109540		Zero_OP	Stranded Far From Home (BOI22_island)	C++14	100 / 100	228 ms	38584 KiB

island

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e5 + 5;

int N, M, a[MAX];
vector<int> adj[MAX];

namespace subtask1{
    bool check(){
        return N <= 2000 && M <= 2000;
    }

    void solve(){
        vector<bool> vis(N);
        auto solve = [&](int s) -> bool{
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
            fill(vis.begin(), vis.end(), false);

            long long have = a[s];
            vis[s] = true;
            for(int u : adj[s]){
                if(!vis[u]){
                    vis[u] = true;
                    pq.push({a[u], u});
                }
            }

            while(!pq.empty()){
                int demand, u;
                tie(demand, u) = pq.top(); pq.pop();
                if(demand > have) return false;
                have += demand;

                for(auto v : adj[u]){
                    if(!vis[v]){
                        vis[v] = true;
                        pq.push({a[v], v});
                    }
                }
            }

            return true;
        };

        for(int i = 0; i < N; ++i){
            cout << solve(i);
        }
    }
}

namespace subtask2{
    bool check(){
        for(int i = 1; i < N; ++i){
            if(a[i - 1] < a[i]) return false;
            int lower = 0;
            for(int j : adj[i]){
                if(j < i){
                    ++lower;
                    if(lower == 2) return false;
                }
            }
        }

        return true;
    }

    int diff[MAX], tin[MAX], tout[MAX], tour[MAX], timer_dfs;
    long long sum_subtree[MAX];

    void block(int l, int r){
        ++diff[l];
        --diff[r + 1];
    }

    void pre_dfs(int u, int p){
        tour[tin[u] = timer_dfs++] = u;
        sum_subtree[u] = a[u];
        for(int v : adj[u]) if(v != p){
            pre_dfs(v, u);
            sum_subtree[u] += sum_subtree[v];
        }

        tout[u] = timer_dfs - 1;
    }

    void dfs_solve(int u, int p){
        for(int v : adj[u]) if(v != p){
            dfs_solve(v, u);

            if(a[u] > sum_subtree[v]){
                block(tin[v], tout[v]);
            }
        }
    }

    void solve(){
        pre_dfs(0, -1);
        dfs_solve(0, -1);

        for(int i = 1; i < N; ++i){
            diff[i] += diff[i - 1];
        }

        vector<bool> answer(N, true);
        for(int i = 0; i < N; ++i){
            if(diff[i] > 0){
                answer[tour[i]] = false;
            }
        }

        for(int i = 0; i < N; ++i){
            cout << answer[i];
        }
    }
}

namespace subtask3{
    bool check(){
        for(int i = 0; i < N; ++i){
            for(int j : adj[i]){
                if(abs(i - j) != 1) return false;
            }
        }
        return true;
    }

    long long pref[MAX];
    pair<int, int> rmq[20][MAX];
    int diff[MAX];

    void block(int l, int r){
        diff[l] += 1;
        diff[r + 1] -= 1;
    }

    pair<int, int> query(int l, int r){
        int k = 31 - __builtin_clz(r - l + 1);
        return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
    }

    long long sum(int l, int r){
        return pref[r] - (l > 0 ? pref[l - 1] : 0);
    }

    void solve(int l, int r){
        if(l >= r) return;

        int mx, mid; tie(mx, mid) = query(l, r);

        if(l < mid){
            if(sum(l, mid - 1) >= mx) solve(l, mid - 1);
            else block(l, mid - 1);
        }

        if(mid < r){
            if(sum(mid + 1, r) >= mx) solve(mid + 1, r);
            else block(mid + 1, r);
        }
    }

    void solve(){
        copy(a, a + N, pref);
        for(int i = 1; i < N; ++i){
            pref[i] += pref[i - 1];
        }

        for(int i = 0; i < N; ++i){
            rmq[0][i] = {a[i], i};
        }

        for(int i = 1; (1 << i) <= N; ++i){
            for(int j = 0; j + (1 << i) - 1 < N; ++j){
                rmq[i][j] = max(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
            }
        }

        solve(0, N - 1);
        for(int i = 1; i < N; ++i) diff[i] += diff[i - 1];
        for(int i = 0; i < N; ++i){
            cout << (diff[i] == 0);
        }
    }
}

namespace subtask5{
    bool check(){
        return true;
    }

    int lab[MAX];
    long long sum[MAX];
    vector<int> candidates[MAX];

    int root(int u){
        return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
    }

    void unite(int u, int v){
        u = root(u);
        v = root(v);
        if(u == v) return;
        if((int)candidates[u].size() < candidates[v].size()) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        sum[u] += sum[v];

        if(candidates[u].empty()) swap(candidates[u], candidates[v]);
        else{
            candidates[u].insert(candidates[u].end(), candidates[v].begin(), candidates[v].end());
        }
    }

    void solve(){
        vector<pair<int, int>> v;
        for(int i = 0; i < N; ++i){
            v.emplace_back(a[i], i);
            lab[i] = -1;
            candidates[i].push_back(i);
            sum[i] = a[i];
        }

        sort(v.begin(), v.end());
        vector<bool> in(N, false);

        for(auto [value, u] : v){
            vector<int> combinable;
            for(auto v : adj[u]){
                if(in[v]){
                    combinable.push_back(root(v));
                }
            }

            sort(combinable.begin(), combinable.end());
            combinable.erase(unique(combinable.begin(), combinable.end()), combinable.end());

            for(auto v : combinable){
                if(sum[v] < a[u]){
                    candidates[v].clear();
                }

                if((int)candidates[u].size() < (int)candidates[v].size()){
                    swap(candidates[u], candidates[v]);
                }

                candidates[u].insert(candidates[u].end(), candidates[v].begin(), candidates[v].end());
                candidates[v].clear();
            }

            for(auto v : combinable){
                unite(v, u);
            }

            in[u] = true;
        }

        vector<bool> answer(N, false);
        int r = root(0);
        for(int cand : candidates[r]){
            answer[cand] = true;
        }

        for(int i = 0; i < N; ++i){
            cout << answer[i];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> N >> M;
    for(int i = 0; i < N; ++i){
        cin >> a[i];
    }

    while(M--){
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    //if(subtask1::check()) return subtask1::solve(), 0;
    //if(subtask2::check()) return subtask2::solve(), 0;
    //if(subtask3::check()) return subtask3::solve(), 0;
    if(subtask5::check()) return subtask5::solve(), 0;

    return 0;
}

Compilation message (stderr)

island.cpp: In function 'void subtask5::unite(int, int)':
island.cpp:204:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |         if((int)candidates[u].size() < candidates[v].size()) swap(u, v);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
island.cpp: In function 'void subtask5::solve()':
island.cpp:227:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  227 |         for(auto [value, u] : v){
      |                  ^

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