Submission #714825

#	Time	Username	Problem	Language	Result	Execution time	Memory
714825		TheSahib	Stranded Far From Home (BOI22_island)	C++14	35 / 100	1074 ms	319072 KiB

island

#include <bits/stdc++.h>


#define ll long long
#define pii pair<int, int>

using namespace std;

const int MAX = 2e5 + 5;
const int oo = 1e9;


struct BIT{
    int tree[MAX];
    BIT(){
        memset(tree, 0, sizeof(tree));
    }
    void update(int pos, int v){
        while(pos < MAX){
            tree[pos] += v;
            pos += pos & -pos;
        }
    }
    int ask(int l, int r){
        if(l != 1) return ask(1, r) - ask(1, l - 1);
        int ans = 0;
        while(r > 0){
            ans += tree[r];
            r -= r & -r;
        }
        return ans;
    }
};

int n, m;
int arr[MAX];
vector<int> g[MAX];


bool visited[MAX];
bool bfs(int start){
    fill(visited, visited + n + 1, 0);
    
    ll cnt = 0;
    
    set<pii> q;
    q.insert({arr[start], start});
    while(!q.empty()){
        int node = q.begin()->second;
        int c = q.begin()->first;
        q.erase(q.begin());
        visited[node] = true;
        if(cnt >= c || node == start){
            cnt += c;
            for(int to:g[node]){
                if(visited[to]) continue;
                q.insert({arr[to], to});
            }
        }
        else{
            return false;
        }
    }
    return true;
}

ll subTree[MAX];
int possible[MAX];
void dfs1(int node, int p){
    ll ans = arr[node];
    for(int to:g[node]){
        if(to == p) continue;
        dfs1(to, node);
        ans += subTree[to];
    }
    subTree[node] = ans;
}

void dfs2(int node, int p){
    if(node == 1){
        possible[node] = 1;
    }
    else{
        possible[node] = (subTree[node] >= arr[p]);
    }
    if(!possible[node]) return;
    for(int to:g[node]){
        if(to == p) continue;
        dfs2(to, node);
    }
}



int main(){
    cin >> n >> m;
    bool chain = true;
    map<int, vector<int>> mp;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        mp[arr[i]].emplace_back(i);
    }
    for (int i = 0; i < m; i++)
    {
        int a, b; cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
        if(abs(a - b) > 1) chain = false;
    }
    if(chain){
        ll preSum[MAX];
        preSum[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            preSum[i] = preSum[i - 1] + arr[i];
        }
        
        BIT fenw;
        for(auto itr = prev(mp.end()); ; itr--){
            for(int a:itr->second){
                int l = a, r = n;
                int rightEnd = n;
                while(l <= r){
                    int mid = (l + r) / 2;
                    if(fenw.ask(a, mid) == 0){
                        l = mid + 1;
                        rightEnd = mid;
                    }
                    else{
                        r = mid - 1;
                    }
                }
                l = 1, r = a;
                int leftEnd = 1;
                while(l <= r){
                    int mid = (l + r) / 2;
                    if(fenw.ask(mid, a) == 0){
                        r = mid - 1;
                        leftEnd = mid;
                    }
                    else{
                        l = mid + 1;
                    }
                }
                ll s = preSum[rightEnd] - preSum[leftEnd - 1];
                possible[a] =   ((s >= arr[rightEnd + 1] && possible[rightEnd + 1]) || 
                                (s >= arr[leftEnd - 1] && possible[leftEnd - 1]) || 
                                (rightEnd - leftEnd + 1 == n));
            }

            for(int a:itr->second){
                fenw.update(a, 1);
            }
            if(itr == mp.begin()) break;
        }
        for (int i = 1; i <= n; i++)
        {
            cout << possible[i];
        }
        
        return 0;
    }
    if(n > 2000 || m > 2000){
        dfs1(1, 1);
        dfs2(1, 1);
        for (int i = 1; i <= n; i++)
        {
            cout << possible[i];
        }
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        cout << bfs(i);
    }
    
}

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