Submission #1270071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270071		shiori_chan	Stranded Far From Home (BOI22_island)	C++17	0 / 100	157 ms	41856 KiB

island

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define compact(v) v.erase(unique(all(v)) , v.end())
#define pi pair<int , int>
#define vi vector<int>
#define eb emplace_back
#define FOR(i , l , r) for(int i = l; i <= r; ++ i)
#define FORD(i , l , r) for(int i = l; i >= r; -- i)

using namespace std;
typedef long long ll;
#define int long long

const int nd = 2e5 + 1 , mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1 , (int)2e9);

template <class T> bool maximize(T &a , T b){return (a < b ? a = b , true : false);}
template <class T> bool minimize(T &a , T b){return (a > b ? a = b , true : false);}


int add(int a , int b) {return (a + b) % mod;}
int mul(int a , int b) {return (a * b) % mod;}
int sub(int a , int b) {return (a - b + mod) % mod;}
int xpow(int a , int b){
    int res = 1;
    for(int i = 0; (1 << i) <= b; ++ i){
        if(b & (1 << i)) res = mul(res , a);
        a = mul(a , a);
    }
    return res;
}

vi adj[nd];
int a[nd];
int ans[nd];
vi s = {-1};
vi node[nd];
unordered_map <int , int> mp;

struct query{
    int x , h;

    bool operator<(const query &o)const{
        return h > o.h;
    }
};

priority_queue <query> q;

struct DSU{
    int par[nd] , sz[nd];

    void init(int n){
        FOR(i , 1 , n) par[i] = i , sz[i] = a[i];
    }

    int get(int u){return (u == par[u] ? u : par[u] = get(par[u]));}

    void join(int u , int v){
        u = get(u) , v = get(v);
        if(u == v) return;

        if(sz[u] > sz[v]) swap(u , v);
        par[u] = v;
        sz[v] += sz[u];
    }
} dsu;

void process_query(int SIZE){
    while(q.size()){
        auto [u , h] = q.top();
        if(h > SIZE) return;
        q.pop();

        ans[u] = dsu.sz[dsu.get(u)];
        if(ans[u] > SIZE) q.push({u , ans[u]});
    }
}

void solve(){
    int n , m;
    cin >> n >> m;
    int total_size = 0;

    FOR(i , 1 , n){
        int v;
        cin >> v;
        a[i] = v;
        total_size += v;

        q.push({i , v});
        s.pb(v);
    }
    dsu.init(n);

    sort(all(s)); compact(s);
    FOR(i , 1 , s.size() - 1) mp[s[i]] = i;

    FOR(i , 1 , n) node[mp[a[i]]].eb(i);

    FOR(i , 1, m){
        int l , r;
        cin >> l >> r;
        adj[l].eb(r) , adj[r].eb(l);
    }

    FOR(i , 1 , s.size() - 1){
        if(q.top().h <= s[i]){
            for(int u : node[i]){
                for(int v : adj[u]) if(a[v] <= a[u]){
                    dsu.join(u , v);
                }
            }

            if(q.top().h == s[i]) process_query(s[i]);
        }
        else{
            process_query(s[i - 1]);

            for(int u : node[i]){
                for(int v : adj[u]) if(a[v] <= a[u]){
                    dsu.join(u , v);
                }
            }
        }
    }

    FOR(i , 1 , n) cout << (ans[i] >= total_size);
}

signed main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);

    #define task "task"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    int test_case = 1;
    while(test_case --) solve();

    return 0;
}
/*
               -.                                                                             ::.            -:       .::::::::::
 ***##*###**##@%***+###+***+**++******#*******#*******++*****+*+=@*+####%@@@@@%*===#*%@===---**#@@#=*######***@@@#*###=*@%#######:
 **##*##*+*%#%@**+**##****************#***+***#*+*+***+++******+=@#+*#=:--===-====-*#+@%:#@@%##*#%#+########+*@%@#*##+=@%######:
 #%####*+*%##@#+*+*###**#********##***#++***++#********#***+++++=%@=###==========:#:#+*@######*%##%#=+###*##*+#@##@%###+=%#####:
 #####***%##@%+***#%#++#######*********++***#*#+##%##****#####+#@ ###===++++=-=@@#**+#%+*+##+#%##%#+*######*+%###@###*=#%####:
 ##*****####@*+***###+=**#+==*+*###%#%###%**%*#=::-+#%####+#=-#+@=-###===+==-#@#*###+=@#+*+##*#%##%##=*######*+@%###%*#*+%###:
 %##***####@#++*+#%+*++=+++=+#**#===-==+*+=:=+@-#+-===-:+#%+:+#:#=@@.#%#----:-###*****#=*@+++***+#%#%#%#+*###*##**@####%@#***%###:
 *####*@##%@++***##+###+====##+##==========-+*@:%+-=-::::::::=@:#=@%+=##**==#@#####*###+=@%=****#+%##@#%#=####*##+#%#####%##**%##:
 #**#*#%##@#*#***##**########*+#*-=*+==+===-++@.%=::+@#+=:.=@*#=#=@%#=*@*####**+*********+@*=+*****%#%*%+*####****@######%**#%#:
 ####*####@++*+*#%+*#**********##*####-====:*=@.#-:####%@@%#####=%#=+@#=+***++*******+#=%@+++*++=*%#@###=*######+@%######@#+###.
 ###**%##@#*****#@*##*#**#***+*******##*==##*=@=%#%##*##*##+*##*-%@%==#@+=*+******#****##+@%+=+***+##%*##*#**##**+@#######@**##:
 ###*#%##@++#*+*##*##****##****#*******####*+=@=%+********#*=*##*-#@#*:*@#=+***+**+++***=@=@@@#=++++=@#@#+%***#####+@#######%#+##.
 ###*#%#%**##+*%#**#*#**#***********#******+=@=%=*++**#**#*+**++-#@*@-=@#=+***+++*+****=#*@ @@#=*##+*#@%++#**#####*%#######@+##:
 ###*###@#**##+*@*************#************#==@+@=+*+++***#+++*++=@@*##:%@#=++++++++++**+*%@@ @@%-=+++##@#=%+*#*#***#%#######%##%:
 ##*#%##@***##+#%**#***#***#********+***#+*#==@#@:=+++++**@=+++++*#@@*%-+@@==++**+**++**++%@@  @@@=-=+##@%=##+#*#***#%###########.
 ##*#%##@*#*##=*%**#*******+***********+*+*+=-@#@-=++++=+%*=+***+@. @###:@%=******+*****=#@@    @@@*:-#@%+=%+#*###+#@###########:
:@#*#%##%#**##+#%+************#*****++***+#*+-%@==+++*=+@=++++==@  @@#%=##%==+*++*+*****=#@@     @@@@#*#@*-@+***##+#%########%#:
 #@*##%@#*###*+#%*##****+***++***++**+++++++*-%@@*=++++=%-==**#@@@@@@##%+#%-=+++++**+**==@@        @#*+@*=##***##+*@###########:
  @*%#%##*##**#%**####*#***********++**+**+*-#@%#-+++=:@=#%##+#@    @@#####@#=++**+******-@=  *@@@@@@@@@@@=+#****#*+@###########:
 @@@%##@#**##*+#%**************+*****+++++++*=#@#@:=+==@@-====*@     @@######@+=+++++++*++=@  @@@@@@@@  +@@=+#****#*=%##########:
  #@@%#@##*###+#@***********+*#*++++++***+*+#=*@#%++=:@@==+*++@@  ..  @@#####%@-=***+*****=@@@@@@   .@@.@ @#=***#+#*=@@##########:
    @%#@#*##**+#@#**#*******+*#++****++++*++#=+@##@ :@@*-+==+@@   .:   @@#####@@=+++++*++**=@@%@@@   -@@@:*@=*#**+#*+@*@#########:
 =:  ##@**####+#@***********+*#++***+++++*++#+=@##@%@@#:=++*@@     ..  #@@#####@#=+**+*+#@@%#@##@@   @  @-=@=****+%*=@-#@%#######:
 : :@@*@##****+#@*+****#****+*%+*****+++++++#==@###%@@-=*+*@@   -*+     =@@#####@*=+**++#= -@%   :  @% -@==@=#***+@*=@% +@@######:
  @@@*+@##**+*+#@#+*******+*++@=+***++**++++**=@##@@*-=+==*.        *::  -@@*####%#-++++##=:%   @-@@%  *@=-@=#***+@+=%@@. @@@%###:
+@@#*+*@##*###=#@#=****#****++@*=*+*++++++++*+=@@@%-:==--+@@@@@@@@#        @@####%*-=+++#+=@@ :       +@+=@+#**++@+=@#%@%- -##%:
 ##%#*#@##**##=#@%+*********+=%#=*++++++*++====@@::-=+##@@@@@@@@@@@@@@      @@@*##%##===++**#@      .. :@*-@%***+*@==@###%@@%####:
 ###%@%@##****=#@@++*#*******=#@=++++*+*+===#@%-:-##+=#@#===@      ::++      =@@***#*#=-==++=@@         @#=#@*+*=#%==@@%#*###%@##.
 #*@ @@@#**###=#@%*+*********+=@+=***+-==#@@+---=+++#@@@@@@@@@                 @@@*+%##*--=+==@+   .    @@+#@*=+=@#==@###%#####.
 **@  @@%****#+#@@#+*********+-@#:====@@#==-===++#@@@@@  @  @@                   @@@+*#+**:-==*@     .  @@**@+=+*%#=+@###########.
 ++@: @@%+*#**++@%@=**+++++===-%@@@@@#=-==+=--+#@@@    @@       . .                @@@@#=+**=--#@       +@**@+==##*-#@###########:
-@@@   @#-======%@*===*###@@@@#=----==+==-=#@@@@ @@*      :@=                        @@@@@#*#=:#@       @*#@==+%#+*#@%##########:
 %@@@@@@#%@@@@@@@%@@@@@%##+=---=+=====-=+@@@#=#*@   ::.+@#:                              :#@@@@#+#@@     @#@@--%#=#*%###########:
%@@  @%@#%##++======------=========#%@@@@=====*=@#%@@%-                             ...       @@@@@@@@#  @*@#:=@#**#*@###########.
   @@%-@*=*#@@@@%#*+*#%@@@@@@@@@@@@@+=--=+***+##@                                  .        .       .*%  @@@:-@##=#+#@#%#########.
 @@@**=@++++=:=%##@@@##%##*+==@%==++******+*#@                                 ..     .  #            @@*:##**##+#%##########%.
+@@#***@+***++@####@*@#=-==+++*+=%@@=+*******++#@=                                 .   ..  =.           @@@.:@*#*##+@%###########
:%#**#%@=**+=%###@@+@#%++******=*@@#=********+%@@                                         .            @@.:@**###*+@###*%#######.
:#+*##@%+**=%###*@+##@#%*=*#***+=@%@++******+++@@                                                     @@:.@@=#**#=@@############.
 ++##%@*++=#@###*%@*##@##%#=+****=#%#=**+*****+%@                                                    @@.=@@@=*##*=@######%######
 #%@@@++=%@#####@#####@*##%+++**+*@%@*=+******+=@+                                          .       @@.#%#@%=###=#%#%####%######
:@@@-@#==@@####*@*#%####@*##%*=+*+=#@#@*=++****+=%@                                        @        %@@@##@@++##=-@###%##########
 +-=@@=+@%####*%###%@*##%==+=#%#%+=+*****==@                                  :=-::         @@@@*#%#@=*#+-@########=@#####
 **%@#*%####*#@%@*%#%##@#*##%@*==+%###@*=+*++*+-@@                           :::                @@%#@###%+#=.@%########+%#####
 #@@########*@@@@%:@%###@%####%@+:##@##%*=+*+++==@                                            :@@%@####@**-:@%######%*#*######
 @%#######**@@#@+=-@%######@######@#=##%##@%==+++==@@                                      @@  =@@%######@@+ =@%#################
=%#######+@@##@#+*=@##%####@%##############@=======@                                     @%@-@@@#######@%: @@##########%#*######
.######*%@@%#%@+**=@#######@.@%##########%**#%#=====*@  :.                                **@@:@@@#####@# +@%#############*######
.#%##+@@@%=#%@#*#**@#%####@:=%@##%##*######*##@*=-==#@   :=@@:                           @ -##-@@@###%-=@%############*##+%#####
:#=*@@#*=+=%#**#+#@#@#####@-==%@**#%#*****##**##%*:--#@       :+%@@@*                     :      @@@#*###################+%#####
 @@###+*#*#@%##*#+%@*%###@=++=%@#*#%#*+********##*-:=@+             @@@@#:             +@       *@@@#############**######*####
 #####***+@@**##**%@@-#%###@=***-%@%***@%#++***#++**###-=%@           @   .-+#%@@@@@@@@@@@@@@        #@@@%#############*#*#####**
 ####%*#*#@#**##*#%@::@%###@=#+#=-##@*+*#@@#*=++##=+**##*=*@%       @@  :::::::.  #@  @@%###@@          @@@@#########**##********
.#####**#@#*####+#@@ #@##%@@=#=%=+=#*@@@@%+%@@@@%*#@===+**+#%@@    @%:.::::::--:: @@ =@*#=#*@@@@          +@@@#*#*******###*###**
 #####**%#**##***@@= @%##@:#+%=@++=#*@* @@@@#*  @@@@#@@+=+****@@@+ :              @@ +@#=:%#@ @@@%           @@@%#######**#**+***
.####**%**###**%@@  @%#@@ #%#=##==#*@@    @@@@@    @@@@@@@+==+*#@@@@@=:    :#@@@ @@ =@#=-###@ #@@@@           @@@@#*************
 ####*#%*#####+#@@  =@%@ @+@#=+#==#*@* .     +@@@@        *@@@*=++==#@@@@@@@:    @@:-@#=-*##@= @@#@@@           #@@@#***********
.#######**###**@@=  @@@@+ ##@#=+#*=##@    ::.     :@@@@@@@-    :@*@@@@@@=       : -@@=#+==+##*@@: %==@@@@           @@@@#****++++
 ######*##*##*@@#  *@@@= @#@@#=++@+##@ +#=    @@@@#+-*%@@@@@@@@@%.       %@@@@@@%= @=@#+===##++=%@:@=:#@@@@           -@@@@%#****
 #####**##*+*#@%  =@%@@.*@@ @%+++=#*@@ .    @@@==@@@@@@-                         .@@@@@+===*+@=## @@@#-+%*@@@:            =@@@*++
 ####***#*+*#@@  :@#@@+ %#@ @@#+++*#@@ -. @@@##@@@#                                  @@@+====@.#@=  @@%==#**@@@-   :=:::.    @@*+
 ##*+*##*++@@@  #@#@@@  @#@  @@#++=*%@   *@%@@@        .                              @@#===#=:@@@   @@@%@@@@@@@@=     .-:   #@*
.##**#****%@@. @@*@@=  .@#@   @@@+=++@  @@%@@@      ......::                            #@@===@  @@@@ ::#@@=         .   .:-.  @@
 #+***++#%@@  @##@@    %@#@ *:  @@@+=*@@@@@@    ....     . ..::.                          @@+-*@  @@@.                ...   .   #
 *#****##% +@*#@%  .: @@#@      :@@@#@@@@     ...  ..         .:.                         @@#=#@  -                   .......
 **++##### @##@@:  ::: =@#@  .:     @@@     ......... .  ..      ..                         @%#*@: # :            .=**=:.. ..:.
 ++*####**#**@@   ::::  @@@@     @@@:    .:.......... ... . .     .:                        -@#+#@ : .:::..:=#%@@@@=    .........
 +######*+*@@*  :::::::   @@@@@@@@    ..:....... .....  .   ...   . .                        %+**%@  ..   #  -**       . . ..:...
 ##**#*+=#@@:  ::::::::. .          :...:........... .  ..         ..                        ##-=#@  .   =@@=            . ......
 ####*+#@@*  :::-::::: ==-=: .::.:::..            ... .. ....       ...                      ##=-=@   :#+.          .::.  ...::::
                                                                                                                                  */

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
island.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35