oj.uz

Submission #654567

# Submission time Handle Problem Language Result Execution time Memory
654567 2022-10-31T18:09:25 Z erto Stranded Far From Home (BOI22_island) C++17
0 / 100
 502 ms 66864 KB 
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define INF (int)(1e9 + 7)
#define INF2 998244353
#define N (ll)(2e5 + 5)
//#define f first
//#define s second
#define int ll
#define lsb(x) (x & (-x))
using namespace std;

int n, m, g, h;
int ans[N];
set<pair<int, int>> v[N];
int a[N];
int p[N], sz[N];
bool used[N];

set<int> ss[N];

int get(int x){
    return p[x] = (p[x] == x ? x : get(p[x]));
}

void unite(int x, int y){
    int a = get(x), b = get(y);
    if(a == b)return;
    if(ss[a].size() < ss[b].size())swap(a, b);
    sz[a] += sz[b];
    p[b] = a;

    for(auto u : ss[b]){
        ss[a].insert(u);
    }
}

void solve(){
    cin >> n >> m;

    int maxx=0;

    for(int i=1; i<=n; i++){
        cin >> a[i];
        if(maxx < a[i]){
            maxx = a[i];
        }
    }

    for(int i=1; i<=m; i++){
        cin >> g >> h;
        v[g].insert({a[h], h});
        v[h].insert({a[g], g});
    }

    priority_queue<pair<int, int>> pq;
    for(int i=1; i<=n; i++){
        pq.push({-a[i], i});
    }

    for(int i=1; i<=n; i++){
        ans[i] = 1;
        sz[i] = a[i];
        p[i] = i;
        ss[i].insert(i);
    }

    while(!pq.empty()){
        auto p = pq.top();
        pq.pop();
        int i = p.second;
        used[i] = 1;
        //cout << i << ' ';

        for(auto z : v[i]){
            int u = z.second;
            //if(i == 4)cout << u << a[u] << sz[get(i)] << '\n';
            
            if(sz[get(i)] >= a[u]){
                if(sz[get(u)] < sz[get(i)]){
                    //cout << i << u << '\n';
                    vector<int> v2;
                    for(int r : ss[get(u)]){
                        if(used[r])v2.push_back(r);
                    }
                    for(int r : v2){
                        ans[r] = 0;
                        ss[get(u)].erase(r);
                    }
                }
                unite(i, u);
            }
        }
    }

    //for(int u : ss[get(maxnode)])ans[u] = 1;


    for(int i=1; i<=n; i++){
        cout << ans[i];
    }
}   


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    for(int i=1; i<=T; i++){
        solve();
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 12 ms 19096 KB Output is correct
3 Correct 11 ms 19140 KB Output is correct
4 Incorrect 12 ms 19540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 10 ms 19104 KB Output is correct
3 Incorrect 283 ms 66864 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Incorrect 383 ms 63168 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Incorrect 502 ms 64940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 12 ms 19096 KB Output is correct
3 Correct 11 ms 19140 KB Output is correct
4 Incorrect 12 ms 19540 KB Output isn't correct
5 Halted 0 ms 0 KB -