oj.uz

Submission #654553

# Submission time Handle Problem Language Result Execution time Memory
654553 2022-10-31T17:31:43 Z erto Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 106672 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] == 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, maxnode;

    for(int i=1; i<=n; i++){
        cin >> a[i];
        if(maxx < a[i]){
            maxx = a[i];
            maxnode = 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;
        bool bb = 0;
        //cout << i << ' ';

        for(auto z : v[i]){
            int u = z.second; 
            if(used[u])continue;
            //if(i == 4)cout << u << a[u] << sz[get(i)] << '\n';
            //cout << i << u << sz[get(i)] << '\n';
            if(sz[get(i)] < a[u]){
                vector<int> v2;
                for(int u : ss[get(i)]){
                    if(used[u])v2.push_back(u);
                }
                for(int u : v2){
                    ans[u] = 0;
                    ss[get(i)].erase(u);
                }
            }
            unite(i, u);
            bb=1;
        }
        //cout  << i << bb<<'\n';
        if(a[i] != maxx && bb == 0){
            vector<int> v2;
            for(int u : ss[get(i)]){
                if(used[u])v2.push_back(u);
            }
            for(int u : v2){
                ans[u] = 0;
                ss[get(i)].erase(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();
    }
}

Compilation message

island.cpp: In function 'void solve()':
island.cpp:41:17: warning: variable 'maxnode' set but not used [-Wunused-but-set-variable]
   41 |     int maxx=0, maxnode;
      |                 ^~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19200 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 278 ms 70156 KB Output is correct
4 Correct 333 ms 80432 KB Output is correct
5 Correct 429 ms 79496 KB Output is correct
6 Correct 426 ms 82152 KB Output is correct
7 Correct 440 ms 82072 KB Output is correct
8 Correct 579 ms 106672 KB Output is correct
9 Correct 393 ms 89904 KB Output is correct
10 Correct 384 ms 64688 KB Output is correct
11 Correct 408 ms 74028 KB Output is correct
12 Correct 444 ms 72676 KB Output is correct
13 Correct 292 ms 77432 KB Output is correct
14 Correct 298 ms 76268 KB Output is correct
15 Correct 272 ms 74064 KB Output is correct
16 Correct 168 ms 73500 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19124 KB Output is correct
2 Incorrect 420 ms 66276 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 Execution timed out 1008 ms 68084 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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