oj.uz

Submission #654570

# Submission time Handle Problem Language Result Execution time Memory
654570 2022-10-31T18:22:56 Z erto Stranded Far From Home (BOI22_island) C++17
100 / 100
 742 ms 141488 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(ss[a], ss[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(a[i] >= a[u]){
                if(sz[get(u)] < a[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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19064 KB Output is correct
2 Correct 10 ms 19020 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 14 ms 19676 KB Output is correct
5 Correct 13 ms 19776 KB Output is correct
6 Correct 12 ms 19640 KB Output is correct
7 Correct 13 ms 19688 KB Output is correct
8 Correct 14 ms 19544 KB Output is correct
9 Correct 15 ms 19660 KB Output is correct
10 Correct 13 ms 19924 KB Output is correct
11 Correct 12 ms 19936 KB Output is correct
12 Correct 12 ms 20036 KB Output is correct
13 Correct 12 ms 19652 KB Output is correct
14 Correct 13 ms 19800 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 314 ms 77332 KB Output is correct
4 Correct 319 ms 79112 KB Output is correct
5 Correct 592 ms 103936 KB Output is correct
6 Correct 644 ms 107580 KB Output is correct
7 Correct 603 ms 107984 KB Output is correct
8 Correct 631 ms 105340 KB Output is correct
9 Correct 543 ms 139816 KB Output is correct
10 Correct 397 ms 72768 KB Output is correct
11 Correct 483 ms 72720 KB Output is correct
12 Correct 623 ms 103512 KB Output is correct
13 Correct 276 ms 76080 KB Output is correct
14 Correct 281 ms 75120 KB Output is correct
15 Correct 287 ms 72740 KB Output is correct
16 Correct 197 ms 72176 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 626 ms 119612 KB Output is correct
3 Correct 595 ms 120972 KB Output is correct
4 Correct 301 ms 74188 KB Output is correct
5 Correct 321 ms 77280 KB Output is correct
6 Correct 618 ms 120228 KB Output is correct
7 Correct 312 ms 74264 KB Output is correct
8 Correct 341 ms 74264 KB Output is correct
9 Correct 189 ms 73704 KB Output is correct
10 Correct 306 ms 78956 KB Output is correct
11 Correct 411 ms 86116 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 718 ms 90688 KB Output is correct
3 Correct 692 ms 98012 KB Output is correct
4 Correct 701 ms 103320 KB Output is correct
5 Correct 690 ms 100908 KB Output is correct
6 Correct 616 ms 86104 KB Output is correct
7 Correct 466 ms 74316 KB Output is correct
8 Correct 196 ms 74188 KB Output is correct
9 Correct 451 ms 65076 KB Output is correct
10 Correct 728 ms 109312 KB Output is correct
11 Correct 440 ms 84672 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19064 KB Output is correct
2 Correct 10 ms 19020 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 14 ms 19676 KB Output is correct
5 Correct 13 ms 19776 KB Output is correct
6 Correct 12 ms 19640 KB Output is correct
7 Correct 13 ms 19688 KB Output is correct
8 Correct 14 ms 19544 KB Output is correct
9 Correct 15 ms 19660 KB Output is correct
10 Correct 13 ms 19924 KB Output is correct
11 Correct 12 ms 19936 KB Output is correct
12 Correct 12 ms 20036 KB Output is correct
13 Correct 12 ms 19652 KB Output is correct
14 Correct 13 ms 19800 KB Output is correct
15 Correct 12 ms 19028 KB Output is correct
16 Correct 11 ms 19028 KB Output is correct
17 Correct 314 ms 77332 KB Output is correct
18 Correct 319 ms 79112 KB Output is correct
19 Correct 592 ms 103936 KB Output is correct
20 Correct 644 ms 107580 KB Output is correct
21 Correct 603 ms 107984 KB Output is correct
22 Correct 631 ms 105340 KB Output is correct
23 Correct 543 ms 139816 KB Output is correct
24 Correct 397 ms 72768 KB Output is correct
25 Correct 483 ms 72720 KB Output is correct
26 Correct 623 ms 103512 KB Output is correct
27 Correct 276 ms 76080 KB Output is correct
28 Correct 281 ms 75120 KB Output is correct
29 Correct 287 ms 72740 KB Output is correct
30 Correct 197 ms 72176 KB Output is correct
31 Correct 11 ms 19028 KB Output is correct
32 Correct 626 ms 119612 KB Output is correct
33 Correct 595 ms 120972 KB Output is correct
34 Correct 301 ms 74188 KB Output is correct
35 Correct 321 ms 77280 KB Output is correct
36 Correct 618 ms 120228 KB Output is correct
37 Correct 312 ms 74264 KB Output is correct
38 Correct 341 ms 74264 KB Output is correct
39 Correct 189 ms 73704 KB Output is correct
40 Correct 306 ms 78956 KB Output is correct
41 Correct 411 ms 86116 KB Output is correct
42 Correct 10 ms 19028 KB Output is correct
43 Correct 718 ms 90688 KB Output is correct
44 Correct 692 ms 98012 KB Output is correct
45 Correct 701 ms 103320 KB Output is correct
46 Correct 690 ms 100908 KB Output is correct
47 Correct 616 ms 86104 KB Output is correct
48 Correct 466 ms 74316 KB Output is correct
49 Correct 196 ms 74188 KB Output is correct
50 Correct 451 ms 65076 KB Output is correct
51 Correct 728 ms 109312 KB Output is correct
52 Correct 440 ms 84672 KB Output is correct
53 Correct 11 ms 19028 KB Output is correct
54 Correct 10 ms 19092 KB Output is correct
55 Correct 9 ms 19028 KB Output is correct
56 Correct 12 ms 19652 KB Output is correct
57 Correct 12 ms 19816 KB Output is correct
58 Correct 12 ms 19668 KB Output is correct
59 Correct 13 ms 19652 KB Output is correct
60 Correct 15 ms 19552 KB Output is correct
61 Correct 11 ms 19668 KB Output is correct
62 Correct 13 ms 19904 KB Output is correct
63 Correct 13 ms 19940 KB Output is correct
64 Correct 14 ms 20036 KB Output is correct
65 Correct 13 ms 19652 KB Output is correct
66 Correct 16 ms 19764 KB Output is correct
67 Correct 323 ms 78856 KB Output is correct
68 Correct 356 ms 80700 KB Output is correct
69 Correct 658 ms 105456 KB Output is correct
70 Correct 669 ms 109104 KB Output is correct
71 Correct 664 ms 109516 KB Output is correct
72 Correct 742 ms 106752 KB Output is correct
73 Correct 595 ms 141488 KB Output is correct
74 Correct 395 ms 74204 KB Output is correct
75 Correct 433 ms 74252 KB Output is correct
76 Correct 660 ms 105048 KB Output is correct
77 Correct 314 ms 77684 KB Output is correct
78 Correct 291 ms 76496 KB Output is correct
79 Correct 325 ms 74332 KB Output is correct
80 Correct 177 ms 73648 KB Output is correct
81 Correct 620 ms 121384 KB Output is correct
82 Correct 616 ms 120980 KB Output is correct
83 Correct 314 ms 73980 KB Output is correct
84 Correct 284 ms 77084 KB Output is correct
85 Correct 610 ms 120036 KB Output is correct
86 Correct 318 ms 74152 KB Output is correct
87 Correct 330 ms 74084 KB Output is correct
88 Correct 332 ms 78680 KB Output is correct
89 Correct 371 ms 85844 KB Output is correct
90 Correct 692 ms 92088 KB Output is correct
91 Correct 692 ms 97876 KB Output is correct
92 Correct 716 ms 103260 KB Output is correct
93 Correct 663 ms 100460 KB Output is correct
94 Correct 563 ms 85876 KB Output is correct
95 Correct 449 ms 73988 KB Output is correct
96 Correct 189 ms 74032 KB Output is correct
97 Correct 451 ms 64928 KB Output is correct
98 Correct 628 ms 108920 KB Output is correct
99 Correct 320 ms 84084 KB Output is correct
100 Correct 326 ms 45336 KB Output is correct
101 Correct 726 ms 102456 KB Output is correct
102 Correct 491 ms 74312 KB Output is correct
103 Correct 571 ms 75824 KB Output is correct
104 Correct 680 ms 88136 KB Output is correct