Submission #1260038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260038		shiori_chan	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	6 ms	10312 KiB

bitaro

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <queue>
#include <stack>
#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;

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

struct segtree{
    vi st; 
    int n;
    stack <pi> update;

    segtree(int _n) : n(_n){
        st.resize((n + 1) * 4 , 0);
    }

    void roll_back(){
        while(update.size()){
            auto [id , v] = update.top(); update.pop(); 
            st[id] = v;
        }
    }

    void up(int id , int l , int r , int x , int v , bool f){
        if(l > x || r < x) return;
        if(l == r){
            if(f) update.push({id , st[id]});
            st[id] = v; 
            return;
        }
        int mid = (r + l) >> 1; 
        up(id * 2 , l , mid , x , v , f); up(id * 2 + 1 , mid + 1 , r , x , v , f);
        if(f) update.push({id , st[id]});
        st[id] = max(st[id * 2] , st[id * 2 + 1]);
    }

    int get(int id , int l , int r , int a , int b){
        if(l > b || r < a) return 0;
        if(a <= l && r <= b) return st[id]; 
        int mid = (r + l) >> 1;
        return max(get(id * 2 , l , mid , a , b) , get(id * 2 + 1 , mid + 1 , r , a , b));
    }
};

vector <segtree> seg;

vi adj[nd] , g[nd];

int component_timer = -1;
bool vs[nd];
int tin[nd] , tout[nd] , d[nd] , in[nd];
int timer = 0;
int component_id[nd];

int bfs_id[nd]; 
int ar_bfs[nd];

void bfs(int x){
    queue <pi> q;
    q.push({x , 0}); 
    int cnt = 0;
    while(q.size()){
        auto [r , pre] = q.front(); q.pop();
        
        bfs_id[r] = ++ cnt;
        ar_bfs[cnt] = r;
        g[bfs_id[r]].clear();

        if(pre) g[bfs_id[pre]].eb(bfs_id[r]);
        
        for(int v : adj[r]){
            -- in[v];
            if(!in[v]) q.push({v , r});
        }
    }
}

void dfs(int r){
    int node = ar_bfs[r];

    tin[node] = ++ timer; 
    component_id[node] = component_timer;
    //cout << r << " " << d[r] << '\n';
    vs[node] = true;

    for(int v : g[r]){
        d[ar_bfs[v]] = d[node] + 1;
        dfs(v);
    }
    tout[node] = timer;
}

void solve(){
    int n , m , q;
    cin >> n >> m >> q;

    FOR(i , 1 , m){
        int u , v; 
        cin >> u >> v;
        adj[v].eb(u);
        ++ in[u];
    }

    FORD(i , n , 1) if(!vs[i]){
        ++ component_timer;
        timer = 0;
        d[i] = 1;
        bfs(i); 
        dfs(1);
        seg.eb(segtree(timer));
    }

    FOR(i , 1 , n){
        segtree &st = seg[component_id[i]];
        st.up(1 , 1 , st.n , tin[i] , d[i] , false);
    }

    while(q --){
        int t , y; cin >> t >> y; 
        segtree &st = seg[component_id[t]];

        FOR(i , 1 , y){
            int s; cin >> s;
            if(component_id[s] != component_id[t]) continue;
            st.up(1 , 1 , st.n , tin[s] , 0 , true);
        }

        int far = st.get(1 , 1 , st.n , tin[t] , tout[t]);
        cout << (!far ? -1 : far - d[t]) << '\n';
        st.roll_back();
    }
}

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);
    }
    solve();

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

Compilation message (stderr)

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

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86