Submission #1317433

#TimeUsernameProblemLanguageResultExecution timeMemory
1317433panhcutizzRailway (BOI17_railway)C++17
0 / 100
157 ms54916 KiB
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <queue>
#include <set>
#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)
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);}

using namespace std;
typedef long long ll;

const int nd = 2e5 + 5 , mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1 , (int)2e9);
int add(int a , int b){
    a += b;
    return (a >= mod ? a - mod : a);
}
int sub(int a , int b){
    a -= b;
    return (a < 0 ? a + mod : a);
}
int mul(ll a , ll b){return (a * b) % mod;}

int xpow(int a , int b){
    if(b == 1) return a;
    int x = xpow(a , b / 2);
    if(b & 1) return mul(a , mul(x , x));
    else return mul(x , x);
}

vector <pi> adj[nd];
int dep[nd] , par[17][nd] , tin[nd] , timer = 0;
int edge[nd];

void dfs(int r , int pre = 0){
    tin[r] = ++ timer;
    dep[r] = dep[pre] + 1;
    par[0][r] = pre;
    for(auto [v , id] : adj[r]) if(v != pre){
        edge[v] = id;
        dfs(v , r);
    }
}

void init(int n){
    FOR(i , 1 , 16)
        FOR(j , 1 , n) par[i][j] = par[i - 1][par[i - 1][j]];
}

void lift(int &u , int mask){
    while(mask){
        int bit = 31 - __builtin_clz(mask);
        u = par[bit][u];
        mask ^= (1 << bit);
    }
}

int get(int u , int v){
    if(dep[u] > dep[v]) swap(u , v);
    lift(v , dep[v] - dep[u]);
    if(u == v) return u;

    FORD(i , 16 , 0) if(par[i][u] != par[i][v]){
        u = par[i][u];
        v = par[i][v];
    }
    
    return par[0][u];
}

set <int> val[nd];
set <int> eliminate[nd];

bool cmp(int a , int b){
    return tin[a] < tin[b];
}

vi ans;
int n , s , k;

void calc(int r , int pre = 0){
    for(auto [v , id] : adj[r]) if(v != pre){
        calc(v , r);
        if(val[v].size() > val[r].size()) swap(val[v] , val[r]);
        for(int u : val[v]) val[r].insert(u);
    }

    for(int u : eliminate[r]) val[r].erase(u);
    if(val[r].size() >= k) ans.eb(edge[r]);
}

void solve(){
    cin >> n >> s >> k;

    FOR(i , 1 , n - 1){
        int u , v;
        cin >> u >> v;
        adj[u].eb(v , i);
        adj[v].eb(u , i);
    }

    dfs(1);
    init(n);
    vi list;

    FOR(i , 1 , s){
        int r;
        cin >> r;
        list.clear();

        FOR(j , 1 , r){
            int u; cin >> u;
            list.eb(u);
        }

        sort(all(list) , cmp);
        int pre_lca = list[0];

        for(int u : list){
            int t = get(u , pre_lca);
            val[u].insert(i);
            eliminate[pre_lca].erase(i);
            eliminate[t].insert(i);
        }
    }

    calc(1);
    cout << ans.size() << '\n';
    for(int e : ans) cout << e << " ";
}

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)

railway.cpp: In function 'int main()':
railway.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...