oj.uz

Submission #654383

# Submission time Handle Problem Language Result Execution time Memory
654383 2022-10-31T08:27:39 Z erto Stranded Far From Home (BOI22_island) C++17
10 / 100
 541 ms 105988 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)ans[i] = 0;
    }

    //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 10 ms 19028 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Incorrect 11 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 11 ms 19132 KB Output is correct
2 Correct 10 ms 19064 KB Output is correct
3 Correct 279 ms 69200 KB Output is correct
4 Correct 313 ms 79440 KB Output is correct
5 Correct 397 ms 79120 KB Output is correct
6 Correct 424 ms 81720 KB Output is correct
7 Correct 421 ms 81620 KB Output is correct
8 Correct 541 ms 105988 KB Output is correct
9 Correct 371 ms 89288 KB Output is correct
10 Correct 380 ms 64196 KB Output is correct
11 Correct 411 ms 73372 KB Output is correct
12 Correct 442 ms 72184 KB Output is correct
13 Correct 297 ms 76864 KB Output is correct
14 Correct 279 ms 75816 KB Output is correct
15 Correct 271 ms 73512 KB Output is correct
16 Correct 174 ms 73020 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Incorrect 459 ms 96232 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 485 ms 77404 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 9 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Incorrect 11 ms 19540 KB Output isn't correct
5 Halted 0 ms 0 KB -