Submission #1109529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109529		Zero_OP	Stranded Far From Home (BOI22_island)	C++14	35 / 100	139 ms	57416 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);
        }
    }
}

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;

    return 0;
}

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