oj.uz

Submission #714825

# Submission time Handle Problem Language Result Execution time Memory
714825 2023-03-25T10:10:01 Z TheSahib Stranded Far From Home (BOI22_island) C++14
35 / 100
 1000 ms 319072 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 277 ms 7612 KB Output is correct
5 Correct 224 ms 7592 KB Output is correct
6 Correct 363 ms 7420 KB Output is correct
7 Correct 261 ms 7552 KB Output is correct
8 Correct 222 ms 7508 KB Output is correct
9 Correct 348 ms 7464 KB Output is correct
10 Correct 8 ms 7508 KB Output is correct
11 Correct 13 ms 7636 KB Output is correct
12 Correct 165 ms 7580 KB Output is correct
13 Correct 8 ms 7380 KB Output is correct
14 Correct 132 ms 7444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 366 ms 45096 KB Output is correct
4 Correct 263 ms 23228 KB Output is correct
5 Correct 334 ms 37976 KB Output is correct
6 Correct 354 ms 33756 KB Output is correct
7 Correct 331 ms 38928 KB Output is correct
8 Correct 327 ms 17852 KB Output is correct
9 Correct 316 ms 33532 KB Output is correct
10 Correct 269 ms 34552 KB Output is correct
11 Correct 235 ms 18520 KB Output is correct
12 Correct 257 ms 17864 KB Output is correct
13 Correct 385 ms 16076 KB Output is correct
14 Correct 377 ms 16064 KB Output is correct
15 Correct 503 ms 37212 KB Output is correct
16 Correct 414 ms 37052 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Correct 669 ms 37020 KB Output is correct
3 Correct 709 ms 32100 KB Output is correct
4 Correct 442 ms 16056 KB Output is correct
5 Correct 408 ms 16112 KB Output is correct
6 Correct 711 ms 37268 KB Output is correct
7 Correct 545 ms 37204 KB Output is correct
8 Correct 552 ms 37236 KB Output is correct
9 Correct 408 ms 36976 KB Output is correct
10 Correct 453 ms 30372 KB Output is correct
11 Correct 401 ms 19984 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Execution timed out 1074 ms 319072 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 277 ms 7612 KB Output is correct
5 Correct 224 ms 7592 KB Output is correct
6 Correct 363 ms 7420 KB Output is correct
7 Correct 261 ms 7552 KB Output is correct
8 Correct 222 ms 7508 KB Output is correct
9 Correct 348 ms 7464 KB Output is correct
10 Correct 8 ms 7508 KB Output is correct
11 Correct 13 ms 7636 KB Output is correct
12 Correct 165 ms 7580 KB Output is correct
13 Correct 8 ms 7380 KB Output is correct
14 Correct 132 ms 7444 KB Output is correct
15 Correct 6 ms 7252 KB Output is correct
16 Correct 3 ms 7252 KB Output is correct
17 Correct 366 ms 45096 KB Output is correct
18 Correct 263 ms 23228 KB Output is correct
19 Correct 334 ms 37976 KB Output is correct
20 Correct 354 ms 33756 KB Output is correct
21 Correct 331 ms 38928 KB Output is correct
22 Correct 327 ms 17852 KB Output is correct
23 Correct 316 ms 33532 KB Output is correct
24 Correct 269 ms 34552 KB Output is correct
25 Correct 235 ms 18520 KB Output is correct
26 Correct 257 ms 17864 KB Output is correct
27 Correct 385 ms 16076 KB Output is correct
28 Correct 377 ms 16064 KB Output is correct
29 Correct 503 ms 37212 KB Output is correct
30 Correct 414 ms 37052 KB Output is correct
31 Correct 5 ms 7252 KB Output is correct
32 Correct 669 ms 37020 KB Output is correct
33 Correct 709 ms 32100 KB Output is correct
34 Correct 442 ms 16056 KB Output is correct
35 Correct 408 ms 16112 KB Output is correct
36 Correct 711 ms 37268 KB Output is correct
37 Correct 545 ms 37204 KB Output is correct
38 Correct 552 ms 37236 KB Output is correct
39 Correct 408 ms 36976 KB Output is correct
40 Correct 453 ms 30372 KB Output is correct
41 Correct 401 ms 19984 KB Output is correct
42 Correct 4 ms 7252 KB Output is correct
43 Execution timed out 1074 ms 319072 KB Time limit exceeded
44 Halted 0 ms 0 KB -