oj.uz

Submission #637903

# Submission time Handle Problem Language Result Execution time Memory
637903 2022-09-03T14:24:30 Z DJeniUp Stranded Far From Home (BOI22_island) C++17
100 / 100
 472 ms 162532 KB 
#include "bits/stdc++.h"
#pragma GCC optimize("O3")

using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define INF 1000000000007
#define N 200007
#define endl '\n'
#define MOD 998244353

ll n,m,a[N],p[N],res[N],s[N],sz[N],h;

vector<ll>v[N];

queue<ll>q[N];

struct D{
    ll s,num;
}d[N];

bool mcp(D d1, D d2){
    return d1.s<d2.s;
}

ll A(ll x){
    if(a[x]!=x)a[x]=A(a[x]);
    return a[x];
}

void S(ll x,ll y,ll z){
    h--;
    //cout<<x<<" "<<y<<" "<<z<<endl;
    while(q[y].size()>0 && s[q[y].front()]<s[z]){
       // cout<<x<<" "<<y<<" "<<z<<" "<<q[y].front()<<" "<<endl;
        if(sz[y]>=s[z])p[q[y].front()]=z;
        q[y].pop();
    }
    if(rand()%2==0){
        swap(x,y);
    }
    if(q[x].size()<q[y].size())swap(q[x],q[y]);
    while(q[y].size()>0){
        q[x].push(q[y].front());
        q[y].pop();
    }
    sz[x]+=sz[y];
    a[y]=x;
   // cout<<q[x].size()<<endl;
    return ;
}

ll R(ll x){
    if(x==0)return 0;
    if(res[x]!=-1)return res[x];
    res[x]=R(p[x]);
    return res[x];
}
 
int main()
{
    cin>>n>>m;
    h=n;
    for(int i=1;i<=n;i++){
        cin>>d[i].s;
        s[i]=d[i].s;
        sz[i]=s[i];
        d[i].num=i;
        a[i]=i;
        res[i]=-1;
        q[i].push(i);
    }
    for(int i=1;i<=m;i++){
        ll x,y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    sort(d+1,d+1+n,mcp);
    for(int i=1;i<=n;i++){
        ll x=d[i].num;
        //cout<<"! "<<x<<endl;
        for(int j=0;j<v[x].size();j++){
            if(s[v[x][j]]<=d[i].s && A(x)!=A(v[x][j])){
                S(A(x),A(v[x][j]),x);
            }
        }
    }
    if(h!=1)exit(1);
    for(int i=1;i<=n;i++){
        //cout<<i<<" "<<p[i]<<endl;
        if(s[i]==d[n].s && h==1)res[i]=1;
    }
    
    for(int i=1;i<=n;i++){
        cout<<R(i);
    }
    cout<<endl;
    
    return 0;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int j=0;j<v[x].size();j++){
      |                     ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 139560 KB Output is correct
2 Correct 85 ms 139592 KB Output is correct
3 Correct 85 ms 139636 KB Output is correct
4 Correct 85 ms 139764 KB Output is correct
5 Correct 85 ms 139816 KB Output is correct
6 Correct 79 ms 139756 KB Output is correct
7 Correct 83 ms 139860 KB Output is correct
8 Correct 84 ms 139832 KB Output is correct
9 Correct 82 ms 139784 KB Output is correct
10 Correct 83 ms 139776 KB Output is correct
11 Correct 83 ms 139944 KB Output is correct
12 Correct 83 ms 139884 KB Output is correct
13 Correct 83 ms 139736 KB Output is correct
14 Correct 82 ms 139752 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 139648 KB Output is correct
2 Correct 79 ms 139612 KB Output is correct
3 Correct 346 ms 158024 KB Output is correct
4 Correct 342 ms 159600 KB Output is correct
5 Correct 388 ms 158852 KB Output is correct
6 Correct 463 ms 159356 KB Output is correct
7 Correct 403 ms 159456 KB Output is correct
8 Correct 448 ms 161276 KB Output is correct
9 Correct 366 ms 159828 KB Output is correct
10 Correct 338 ms 158532 KB Output is correct
11 Correct 343 ms 160632 KB Output is correct
12 Correct 405 ms 158244 KB Output is correct
13 Correct 315 ms 158648 KB Output is correct
14 Correct 323 ms 158584 KB Output is correct
15 Correct 355 ms 158392 KB Output is correct
16 Correct 277 ms 158328 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 139660 KB Output is correct
2 Correct 398 ms 156832 KB Output is correct
3 Correct 420 ms 158376 KB Output is correct
4 Correct 378 ms 158668 KB Output is correct
5 Correct 319 ms 158672 KB Output is correct
6 Correct 418 ms 158372 KB Output is correct
7 Correct 408 ms 158384 KB Output is correct
8 Correct 405 ms 158400 KB Output is correct
9 Correct 282 ms 158248 KB Output is correct
10 Correct 341 ms 159280 KB Output is correct
11 Correct 336 ms 158716 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 139560 KB Output is correct
2 Correct 465 ms 158200 KB Output is correct
3 Correct 464 ms 159560 KB Output is correct
4 Correct 448 ms 159584 KB Output is correct
5 Correct 468 ms 159592 KB Output is correct
6 Correct 439 ms 158828 KB Output is correct
7 Correct 354 ms 162532 KB Output is correct
8 Correct 293 ms 160240 KB Output is correct
9 Correct 300 ms 152660 KB Output is correct
10 Correct 433 ms 159652 KB Output is correct
11 Correct 360 ms 158776 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 139560 KB Output is correct
2 Correct 85 ms 139592 KB Output is correct
3 Correct 85 ms 139636 KB Output is correct
4 Correct 85 ms 139764 KB Output is correct
5 Correct 85 ms 139816 KB Output is correct
6 Correct 79 ms 139756 KB Output is correct
7 Correct 83 ms 139860 KB Output is correct
8 Correct 84 ms 139832 KB Output is correct
9 Correct 82 ms 139784 KB Output is correct
10 Correct 83 ms 139776 KB Output is correct
11 Correct 83 ms 139944 KB Output is correct
12 Correct 83 ms 139884 KB Output is correct
13 Correct 83 ms 139736 KB Output is correct
14 Correct 82 ms 139752 KB Output is correct
15 Correct 81 ms 139648 KB Output is correct
16 Correct 79 ms 139612 KB Output is correct
17 Correct 346 ms 158024 KB Output is correct
18 Correct 342 ms 159600 KB Output is correct
19 Correct 388 ms 158852 KB Output is correct
20 Correct 463 ms 159356 KB Output is correct
21 Correct 403 ms 159456 KB Output is correct
22 Correct 448 ms 161276 KB Output is correct
23 Correct 366 ms 159828 KB Output is correct
24 Correct 338 ms 158532 KB Output is correct
25 Correct 343 ms 160632 KB Output is correct
26 Correct 405 ms 158244 KB Output is correct
27 Correct 315 ms 158648 KB Output is correct
28 Correct 323 ms 158584 KB Output is correct
29 Correct 355 ms 158392 KB Output is correct
30 Correct 277 ms 158328 KB Output is correct
31 Correct 80 ms 139660 KB Output is correct
32 Correct 398 ms 156832 KB Output is correct
33 Correct 420 ms 158376 KB Output is correct
34 Correct 378 ms 158668 KB Output is correct
35 Correct 319 ms 158672 KB Output is correct
36 Correct 418 ms 158372 KB Output is correct
37 Correct 408 ms 158384 KB Output is correct
38 Correct 405 ms 158400 KB Output is correct
39 Correct 282 ms 158248 KB Output is correct
40 Correct 341 ms 159280 KB Output is correct
41 Correct 336 ms 158716 KB Output is correct
42 Correct 79 ms 139560 KB Output is correct
43 Correct 465 ms 158200 KB Output is correct
44 Correct 464 ms 159560 KB Output is correct
45 Correct 448 ms 159584 KB Output is correct
46 Correct 468 ms 159592 KB Output is correct
47 Correct 439 ms 158828 KB Output is correct
48 Correct 354 ms 162532 KB Output is correct
49 Correct 293 ms 160240 KB Output is correct
50 Correct 300 ms 152660 KB Output is correct
51 Correct 433 ms 159652 KB Output is correct
52 Correct 360 ms 158776 KB Output is correct
53 Correct 80 ms 139676 KB Output is correct
54 Correct 84 ms 139604 KB Output is correct
55 Correct 79 ms 139660 KB Output is correct
56 Correct 83 ms 139852 KB Output is correct
57 Correct 82 ms 139876 KB Output is correct
58 Correct 81 ms 139816 KB Output is correct
59 Correct 81 ms 139772 KB Output is correct
60 Correct 83 ms 139788 KB Output is correct
61 Correct 82 ms 139868 KB Output is correct
62 Correct 80 ms 139776 KB Output is correct
63 Correct 82 ms 139880 KB Output is correct
64 Correct 79 ms 139776 KB Output is correct
65 Correct 83 ms 139844 KB Output is correct
66 Correct 82 ms 139832 KB Output is correct
67 Correct 360 ms 159356 KB Output is correct
68 Correct 338 ms 159604 KB Output is correct
69 Correct 386 ms 158744 KB Output is correct
70 Correct 407 ms 159396 KB Output is correct
71 Correct 400 ms 159416 KB Output is correct
72 Correct 452 ms 161200 KB Output is correct
73 Correct 359 ms 159820 KB Output is correct
74 Correct 341 ms 158388 KB Output is correct
75 Correct 311 ms 160656 KB Output is correct
76 Correct 399 ms 158176 KB Output is correct
77 Correct 318 ms 158632 KB Output is correct
78 Correct 312 ms 158604 KB Output is correct
79 Correct 349 ms 158504 KB Output is correct
80 Correct 275 ms 158292 KB Output is correct
81 Correct 414 ms 158352 KB Output is correct
82 Correct 418 ms 158392 KB Output is correct
83 Correct 389 ms 158648 KB Output is correct
84 Correct 319 ms 158612 KB Output is correct
85 Correct 424 ms 158332 KB Output is correct
86 Correct 394 ms 158388 KB Output is correct
87 Correct 388 ms 158572 KB Output is correct
88 Correct 343 ms 159236 KB Output is correct
89 Correct 342 ms 158792 KB Output is correct
90 Correct 468 ms 159596 KB Output is correct
91 Correct 472 ms 159672 KB Output is correct
92 Correct 457 ms 159624 KB Output is correct
93 Correct 453 ms 159576 KB Output is correct
94 Correct 437 ms 158772 KB Output is correct
95 Correct 354 ms 162496 KB Output is correct
96 Correct 289 ms 160128 KB Output is correct
97 Correct 287 ms 152628 KB Output is correct
98 Correct 408 ms 159560 KB Output is correct
99 Correct 339 ms 158756 KB Output is correct
100 Correct 189 ms 145820 KB Output is correct
101 Correct 460 ms 159396 KB Output is correct
102 Correct 401 ms 156792 KB Output is correct
103 Correct 412 ms 157876 KB Output is correct
104 Correct 455 ms 159400 KB Output is correct