Submission #1109515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109515		Zero_OP	Stranded Far From Home (BOI22_island)	C++14	20 / 100	143 ms	37192 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];
        }
    }
}

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;

    return 0;
}

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