oj.uz

Submission #714822

# Submission time Handle Problem Language Result Execution time Memory
714822 2023-03-25T10:07:27 Z TheSahib Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 365668 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 227 ms 7608 KB Output is correct
5 Correct 197 ms 7508 KB Output is correct
6 Correct 350 ms 7420 KB Output is correct
7 Correct 244 ms 7556 KB Output is correct
8 Correct 179 ms 7548 KB Output is correct
9 Correct 331 ms 7356 KB Output is correct
10 Correct 9 ms 7488 KB Output is correct
11 Correct 7 ms 7636 KB Output is correct
12 Correct 125 ms 7584 KB Output is correct
13 Correct 8 ms 7380 KB Output is correct
14 Correct 116 ms 7436 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7276 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 343 ms 45112 KB Output is correct
4 Correct 227 ms 23252 KB Output is correct
5 Correct 336 ms 37864 KB Output is correct
6 Correct 355 ms 33668 KB Output is correct
7 Correct 357 ms 38972 KB Output is correct
8 Correct 313 ms 17920 KB Output is correct
9 Correct 292 ms 33508 KB Output is correct
10 Correct 240 ms 34372 KB Output is correct
11 Correct 204 ms 18400 KB Output is correct
12 Correct 223 ms 17764 KB Output is correct
13 Correct 332 ms 16164 KB Output is correct
14 Correct 363 ms 16136 KB Output is correct
15 Correct 451 ms 37260 KB Output is correct
16 Incorrect 390 ms 36944 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 604 ms 37040 KB Output is correct
3 Correct 579 ms 36556 KB Output is correct
4 Correct 375 ms 20632 KB Output is correct
5 Correct 380 ms 19156 KB Output is correct
6 Correct 740 ms 41876 KB Output is correct
7 Correct 524 ms 41640 KB Output is correct
8 Correct 504 ms 41676 KB Output is correct
9 Incorrect 403 ms 40724 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Execution timed out 1099 ms 365668 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 227 ms 7608 KB Output is correct
5 Correct 197 ms 7508 KB Output is correct
6 Correct 350 ms 7420 KB Output is correct
7 Correct 244 ms 7556 KB Output is correct
8 Correct 179 ms 7548 KB Output is correct
9 Correct 331 ms 7356 KB Output is correct
10 Correct 9 ms 7488 KB Output is correct
11 Correct 7 ms 7636 KB Output is correct
12 Correct 125 ms 7584 KB Output is correct
13 Correct 8 ms 7380 KB Output is correct
14 Correct 116 ms 7436 KB Output is correct
15 Correct 4 ms 7276 KB Output is correct
16 Correct 4 ms 7252 KB Output is correct
17 Correct 343 ms 45112 KB Output is correct
18 Correct 227 ms 23252 KB Output is correct
19 Correct 336 ms 37864 KB Output is correct
20 Correct 355 ms 33668 KB Output is correct
21 Correct 357 ms 38972 KB Output is correct
22 Correct 313 ms 17920 KB Output is correct
23 Correct 292 ms 33508 KB Output is correct
24 Correct 240 ms 34372 KB Output is correct
25 Correct 204 ms 18400 KB Output is correct
26 Correct 223 ms 17764 KB Output is correct
27 Correct 332 ms 16164 KB Output is correct
28 Correct 363 ms 16136 KB Output is correct
29 Correct 451 ms 37260 KB Output is correct
30 Incorrect 390 ms 36944 KB Output isn't correct
31 Halted 0 ms 0 KB -