oj.uz

Submission #630182

# Submission time Handle Problem Language Result Execution time Memory
630182 2022-08-15T21:24:44 Z kderylo Stranded Far From Home (BOI22_island) C++17
100 / 100
 348 ms 42060 KB 
#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int stala=2e5+10;
long long war[stala];
int ojciec[stala];
int wys[stala];
int reprezentant[stala];
long long suma[stala];
set<pair<long long,pair<int,int> > >secik; //mniejsza wartosc/wieksza wartosc
vector<int>wektor[stala];
vector<int>w[stala];//0 - zablokowana/1 - wolna
bool o[stala];
int korzen=1;
int Find(int a){
    if(ojciec[a]!=a){
        return Find(ojciec[a]);
    }
    else{
        return a;
    }
}
void Union(int a,int b){
    int do_wstawienia;
    a=Find(a);
    b=Find(b);
    if(war[reprezentant[a]]>war[reprezentant[b]]){
        wektor[reprezentant[a]].push_back(reprezentant[b]);
        do_wstawienia=reprezentant[a];
        if(suma[b]>=war[reprezentant[a]]){
            w[reprezentant[a]].push_back(1);
        }
        else{
            w[reprezentant[a]].push_back(0);
        }
    }
    else{
        wektor[reprezentant[b]].push_back(reprezentant[a]);
        do_wstawienia=reprezentant[b];
        if(suma[a]>=war[reprezentant[b]]){
            w[reprezentant[b]].push_back(1);
        }
        else{
            w[reprezentant[b]].push_back(0);
        }
    }

    if(wys[a]<wys[b]){
        ojciec[a]=b;
        wys[b]=max(wys[b],wys[a]+1);
        suma[b]+=suma[a];
        reprezentant[b]=do_wstawienia;
    }
    else{
        ojciec[b]=a;
        wys[a]=max(wys[a],wys[b]+1);
        suma[a]+=suma[b];
        reprezentant[a]=do_wstawienia;
    }
    korzen=do_wstawienia;
}
void dfs(int k){
    o[k]=1;
    for(int i=0;i<(int)wektor[k].size();i++){
        if(w[k][i]==1){
            dfs(wektor[k][i]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile,drogi;
    cin>>ile>>drogi;
    for(int i=1;i<=ile;i++){
        cin>>war[i];
    }
    for(int i=1;i<=ile;i++){
        ojciec[i]=i;
        wys[i]=1;
        reprezentant[i]=i;
        suma[i]=war[i];
    }
    for(int i=1;i<=drogi;i++){
        int a,b;//a - wartosc mniejsza/b - wartosc wieksza
        cin>>a>>b;
        long long pom=max(war[a],war[b]);
        if(war[a]>war[b]){
            swap(a,b);
        }
        secik.insert(make_pair(pom,make_pair(a,b)));
    }
    while(!secik.empty()){
        int w1=secik.begin()->second.first;
        int w2=secik.begin()->second.second;
        if(Find(w1)!=Find(w2)){
            Union(w1,w2);
        }
        secik.erase(secik.begin());
    }
    dfs(korzen);
    for(int i=1;i<=ile;i++){
        cout<<o[i];
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9940 KB Output is correct
5 Correct 7 ms 9996 KB Output is correct
6 Correct 6 ms 9996 KB Output is correct
7 Correct 6 ms 9996 KB Output is correct
8 Correct 6 ms 9992 KB Output is correct
9 Correct 6 ms 9992 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 5 ms 9940 KB Output is correct
13 Correct 6 ms 9944 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9688 KB Output is correct
3 Correct 249 ms 36284 KB Output is correct
4 Correct 194 ms 31636 KB Output is correct
5 Correct 291 ms 31716 KB Output is correct
6 Correct 292 ms 32468 KB Output is correct
7 Correct 273 ms 32464 KB Output is correct
8 Correct 271 ms 37196 KB Output is correct
9 Correct 238 ms 32320 KB Output is correct
10 Correct 172 ms 33268 KB Output is correct
11 Correct 198 ms 37156 KB Output is correct
12 Correct 247 ms 31712 KB Output is correct
13 Correct 196 ms 30960 KB Output is correct
14 Correct 191 ms 31544 KB Output is correct
15 Correct 241 ms 41924 KB Output is correct
16 Correct 134 ms 40908 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 270 ms 32488 KB Output is correct
3 Correct 313 ms 32460 KB Output is correct
4 Correct 211 ms 37280 KB Output is correct
5 Correct 208 ms 31100 KB Output is correct
6 Correct 274 ms 32580 KB Output is correct
7 Correct 275 ms 41932 KB Output is correct
8 Correct 239 ms 42060 KB Output is correct
9 Correct 133 ms 40944 KB Output is correct
10 Correct 215 ms 36484 KB Output is correct
11 Correct 227 ms 30960 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 309 ms 32824 KB Output is correct
3 Correct 306 ms 32484 KB Output is correct
4 Correct 304 ms 32540 KB Output is correct
5 Correct 273 ms 32556 KB Output is correct
6 Correct 282 ms 32568 KB Output is correct
7 Correct 213 ms 38304 KB Output is correct
8 Correct 143 ms 36428 KB Output is correct
9 Correct 240 ms 28132 KB Output is correct
10 Correct 256 ms 30924 KB Output is correct
11 Correct 224 ms 30964 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9940 KB Output is correct
5 Correct 7 ms 9996 KB Output is correct
6 Correct 6 ms 9996 KB Output is correct
7 Correct 6 ms 9996 KB Output is correct
8 Correct 6 ms 9992 KB Output is correct
9 Correct 6 ms 9992 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 5 ms 9940 KB Output is correct
13 Correct 6 ms 9944 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9688 KB Output is correct
17 Correct 249 ms 36284 KB Output is correct
18 Correct 194 ms 31636 KB Output is correct
19 Correct 291 ms 31716 KB Output is correct
20 Correct 292 ms 32468 KB Output is correct
21 Correct 273 ms 32464 KB Output is correct
22 Correct 271 ms 37196 KB Output is correct
23 Correct 238 ms 32320 KB Output is correct
24 Correct 172 ms 33268 KB Output is correct
25 Correct 198 ms 37156 KB Output is correct
26 Correct 247 ms 31712 KB Output is correct
27 Correct 196 ms 30960 KB Output is correct
28 Correct 191 ms 31544 KB Output is correct
29 Correct 241 ms 41924 KB Output is correct
30 Correct 134 ms 40908 KB Output is correct
31 Correct 4 ms 9684 KB Output is correct
32 Correct 270 ms 32488 KB Output is correct
33 Correct 313 ms 32460 KB Output is correct
34 Correct 211 ms 37280 KB Output is correct
35 Correct 208 ms 31100 KB Output is correct
36 Correct 274 ms 32580 KB Output is correct
37 Correct 275 ms 41932 KB Output is correct
38 Correct 239 ms 42060 KB Output is correct
39 Correct 133 ms 40944 KB Output is correct
40 Correct 215 ms 36484 KB Output is correct
41 Correct 227 ms 30960 KB Output is correct
42 Correct 5 ms 9684 KB Output is correct
43 Correct 309 ms 32824 KB Output is correct
44 Correct 306 ms 32484 KB Output is correct
45 Correct 304 ms 32540 KB Output is correct
46 Correct 273 ms 32556 KB Output is correct
47 Correct 282 ms 32568 KB Output is correct
48 Correct 213 ms 38304 KB Output is correct
49 Correct 143 ms 36428 KB Output is correct
50 Correct 240 ms 28132 KB Output is correct
51 Correct 256 ms 30924 KB Output is correct
52 Correct 224 ms 30964 KB Output is correct
53 Correct 5 ms 9728 KB Output is correct
54 Correct 4 ms 9684 KB Output is correct
55 Correct 5 ms 9732 KB Output is correct
56 Correct 6 ms 9992 KB Output is correct
57 Correct 6 ms 9992 KB Output is correct
58 Correct 7 ms 9940 KB Output is correct
59 Correct 6 ms 9940 KB Output is correct
60 Correct 7 ms 9940 KB Output is correct
61 Correct 6 ms 9940 KB Output is correct
62 Correct 7 ms 10024 KB Output is correct
63 Correct 6 ms 9940 KB Output is correct
64 Correct 6 ms 9940 KB Output is correct
65 Correct 6 ms 9940 KB Output is correct
66 Correct 6 ms 9940 KB Output is correct
67 Correct 233 ms 36244 KB Output is correct
68 Correct 208 ms 31568 KB Output is correct
69 Correct 244 ms 31876 KB Output is correct
70 Correct 308 ms 32452 KB Output is correct
71 Correct 250 ms 32476 KB Output is correct
72 Correct 267 ms 37220 KB Output is correct
73 Correct 217 ms 32268 KB Output is correct
74 Correct 190 ms 33184 KB Output is correct
75 Correct 230 ms 37136 KB Output is correct
76 Correct 241 ms 31640 KB Output is correct
77 Correct 212 ms 30920 KB Output is correct
78 Correct 239 ms 31564 KB Output is correct
79 Correct 241 ms 41940 KB Output is correct
80 Correct 141 ms 40920 KB Output is correct
81 Correct 289 ms 32452 KB Output is correct
82 Correct 311 ms 32532 KB Output is correct
83 Correct 239 ms 37428 KB Output is correct
84 Correct 220 ms 30880 KB Output is correct
85 Correct 309 ms 32608 KB Output is correct
86 Correct 280 ms 41948 KB Output is correct
87 Correct 247 ms 41948 KB Output is correct
88 Correct 246 ms 36548 KB Output is correct
89 Correct 242 ms 31024 KB Output is correct
90 Correct 332 ms 32896 KB Output is correct
91 Correct 343 ms 32512 KB Output is correct
92 Correct 348 ms 32468 KB Output is correct
93 Correct 301 ms 32588 KB Output is correct
94 Correct 288 ms 32480 KB Output is correct
95 Correct 272 ms 38384 KB Output is correct
96 Correct 143 ms 36516 KB Output is correct
97 Correct 231 ms 28148 KB Output is correct
98 Correct 274 ms 30788 KB Output is correct
99 Correct 229 ms 30928 KB Output is correct
100 Correct 154 ms 24436 KB Output is correct
101 Correct 306 ms 32604 KB Output is correct
102 Correct 284 ms 31884 KB Output is correct
103 Correct 269 ms 33680 KB Output is correct
104 Correct 347 ms 33396 KB Output is correct