Submission #1261424

#TimeUsernameProblemLanguageResultExecution timeMemory
1261424duccnammMergers (JOI19_mergers)C++20
0 / 100
3095 ms327680 KiB
//********###############***************+*******#####################*********************###**************#######****************+++++++****************+++ //********##############*****************+******#################**##*******++*******************+*+*******#######****************+++++++++***************++ //*******###############*****************+******#################**#********++******+***********+*++********#*####****************+++++++++***************++ //******###############*************************###*#############***#*******++******+***********+++++++****************************++++++++***************++ //*****#################************************##**##***#######****#*****+*++******+*+****+++====+++*******************************+++++++***************++ //*****##################***********************###*******#######*****+++++++=*****+=*+++++*++++==------==+++***********************++++******************++ //*******################********##************####*******#*###******+++++++==+****+-+-=+==-::..........:::::--+*****************************************+++ //**+*******#############*****#*####***********######****###*+-:..:.......::--=--=+=:+*=-::..........::::::::::::-+*************************************++++ //+++++******########********##**###***********#*#***###+-...::::::::::::::::::::::::::::..........::::::::::::-:::-=***#********************************+++ //+++++******########************##************##**#+-....::...::::::.::::::---:::::::::........:...::::--==----:::::::=*#********************************** //+++++******#######**************#***************-..........::::::::----------=+=-::---:::::::::::::::::::--=++++==-::::-+=+******************************* //++++******######**********#*************++++=:..........:::::::::::::::::::-===+-:+--:::::.........::-----:----==+*+-::-+**++**************+++**++****** //*+++*******#####***********#***********++++=:.:......::::--::::::::::::------=**++#*=-==----:::::::.::.:::-==-------=++-:::+*+++***********++++++++++**+++ //**++*******######********##*************+-::::....:::::-=::::::::::-----=-===:*#+#%*+*+==-----:::::::::-=-::--==-:----=+*=::-+++++*********+++++++++++++++ //**++*+******#####*********##**********+:::::::::---:-==::::::::-:----====+=+++++*%+=#*+++=----:::::::::::-==----==-------+*+:.-+++********++++++++++++++++ //**+++++*****#####******************#+-:-----:-=--:-==::::::::::---===+*###**+***#*=*#*==----:::::.::::-=----+=:=:-===--===-**=::+*++******++++++++++++++++ //***++++*****#####*****#######*****=::-------=+--=+-::::::::::-:--==+*###%%%##%#+#*-**=-------===-::::::---=-+*+-==:-=+=-=++-=**-.-++*+**++++++++++++++++++ //***+*******######****#########**+::----==-=++-=*+:--:::::::::--===+**+*=#%%%%%##%+=#+--+###+=:----::::---:-=-+*++++---=+==++=-+*+::++*++++++++++++++++++++ //**+*******#######***#########**+:---=++--++=-+*+---:::::::::-====++*#%%%*@%%%%*%#==+++*===+*##+--=::-+-----=+-+*+**+=-==+===+=-=*+::++++++++++++++++++++++ //*+++******#######***#######***+::--=+=-=++=+*+=:--::::::::-----=+++*#%%%*%%%#*#%#==+==----:::-=--+*--=+==-==+==*****+=-=++===++=-++-:=++++++++++++++++++++ //+++++****######******####****-::-==++=++++**+=-=-::--:::---:--==******#######*#%#=+***++=-::::::--====+====+++==***+++===+++==++===+=-==++++++++++++++++++ //++++++***######************+-:--=+++==+++**++==-::--------:--==++**########****#*+*#****#*+=--::----==++==+++++=+*#**+++==+===++====+=--==++++++++++++++++ //++++++***######*********++=:---=+===++++***++==---==---=:-:--=+++#%%%%%%%%%%#*++*###########+===----===++=++++++=+###**++==++==++====+=-===+*+++++++++++++ //+++++****#######*******++----===+==++++***++++--====--===---==***%%@@@@@%%@%##***###%%%%%%%%#*=====-====+++++**++=+#%#*#*+==++==++===++==++==*****++++**** //+++++****#######******++--====+++++**++****++=-=*==--===+--==+#%%@@@@@@%%%%%%#**####%%%%%%%%%#+=+++===++++++*+**+++*#####*+==+==++====++==++==+##********* //++++*****########******-=====++++++*****+**++==*+==--==++-==+#%@%@@@@@%%%%%%###*#####%%%%%%%%%*++++=+=+++++++*+**+++*#####*+=====++====*+=-===--=****##*** //++++****#########*****==+++=+++++++*******++=+**++=-=++++=++#%%%@@@%%%####*******####%###%%%%#*++*++++++++*++++**+++*#%%###*+====+++===+++=-------+******* //++++*****#########****=++++=+++*+********++++*++++===+++=+*#%%%%%%###*+++++++====++********###*****++++*+***++*****++*%%###**=====+++=+=+++==-----=*##**** //++++*****#########**#+=+++++**++**********+++*++*===+*+++**#%%####***+=====--------=====++******#*++****++*#*+*****++*#%%#%#*+==+=+++=+==++==----=+****#** //+++*****##########**#+++++++++*****#*****+++*++++===+++++*##%%###**+===------:::::----====+++*****++*******#*++**+****###%##**+=+==++=++++++=====+++====-: //****########*#######*++++++++****##+*****++**++*++++++=+***####**++=------::::::::::-----===++****+********##++##**#**##%%##**+=++=+*++++++++======----::: //****################*+*++*++******+******++*++**++++**+**#*****+++==---::::::::::::::::----===++******#****##**##**##*##%%%#***+++=+*++++++=+=--==-::::::. //***########*####%%%%#+*+*+++*******##*##*++*++**++*******#****+++===---:::::::::::::::::----==++****#*##*##*##*###*##**#%%%%#**+++++**+++*++==-:-=-::..... //***########*###%%%@@%+#****+**+***###*#**+**+****+*******#****++====--::::::::::::::::::::---==+**#***############**#**#%%%%*#*++*+***++*#*++=-:.:-:...... //****######**##%%@@@@@*#****++****######******#***+**+****#***++===-----:::::::.....:.::::---==+**##*####################%%%%##*++*****+++##*++-::.:-:..... //****##*###**##%%@@@@@*#**++***#*###*###****###********#***#**++====-----:::::::::::::::-----=++*###*####################%%%###*++*****+++*#*++=::..::..... //*******#######%%@@@@@%*#*+++****#*#####****######**#*##***#*+====-----:::::::::...::::::---===+*########%####%##########%%####*++*#****++*#**++-.....:.... //*******###*###%%@@@@@%#*+**+*#*###%%###**#############****##*++========------::::::::::::----=+*#######%%%###%#######%%#%%####*++##********##*+=.......... //********######%%@@@@@%%****+*#*########**#####*########*+*#*+=-----:::::::::::::::::::::::---+*##**#*####%###%#######%%#%%####*+*###*#******#*++:...:::::: //********##*###%%@@@@@%@#***+***#%#%%%%#**######%%#####**+***+==------::::::::::::..::::::::-=*###**#*########%######%%%#%%%%##***#%#*********#*+-..::::::: //********###*##%%@@@@@@@%#**+***##%%%%%#**#####%%#######***###********+==-::::::::::::::::::-*######%#%%%%%%%%%%#####%%%#%%%%##***%%#*****##*+***=::::::::: //*******###**##%@@@@@@@@%*#*****###%%%%*#*#####%%%#######*########%%%###+===-:::::::::::::--=*#%%%%%%%%%%%%%%%%%%#####%%%%%%%##***%%#*****##*++*++::::::::: //*******#######%%@@@@@@@####*+**###%%%%####%##%%%%#########*##****+*++++=====-::::::::::--=+**##%%%%%%%%%###%%%%#######%%%%%%##**##%#*#***##**++**-:::::::: //***#######*###%%@@@@@@%%##*++**###%@%%#%##%#%%#%####*#%###++**+++=====----=--:::::::::--==+++**#%###%%%##*###%%%######%%%%%%#**###%%##***###*++**-:::::::: //***#######*###%%@@@@@@%%%#*++*+##%%%%#*#####%%%%#*****####*=+*++++=====------:::::::::---======+*####%%%#**#####**#####%%%%%#####%%%##**#####*=+*-:------- //**########*##%@@@@@@@%%%##++*+###%%%####%%%%%%%###**++**##*+**+++=========---::::::::------====+++**#%%%%%#####***####%%%%%#####%%%##*######*=*:-------- //***#######**##%@@@@@@@%%%%#*+***##%%%#%#%%%%%%%%#***+==+#*##*****+++===++===---::::::------========+++**#####%%##*****##%%%%#####%%%##**#%%##*+*=:::------ //***#######**##%@@@@@@@%%%%#*****##%%%%%#%%%%#%%%#**++=-=**####*#*+++++++++++==--:::::---=======+++++++****+++++*##******%%%####%#%%%##*##%%##*++::::------ //***######***##%@@@@@@@@@%%%*****######%%%%%%#%%##**++===+####%%%%%%%%#*++++++=--:::::---==++++++*%%@@%%##*+++====+**++++*%%%%##%%%%%##*#%%%%#*+-:-:------- //***######**###%@@@@@@@%@%%%#**#**##%%%@#%%#%%%##**+====++*##%#*#%%%*##***+++++=-::::::--=++++*#*+#%#*#*=+#**++=----=====+#%%%%#%%%%%####%%%##+=-----====-- //***######**###%%@@@@@@%@%%%#**###*%##%%###%%%##*++=======+**##**#%%%#++*##==++=-::..::-==+==*#*+=#%###*+*++++==--------==+#%%%%#%%%####%#%%#*==-=-======-: //***######**###%%%@@@@@@@%%%%**%%%######*####**++==--------=+***++=======----==-::....:--======+++++====-----------:::::--=*%%%%##%%%%%%%#%%#+=+=====----:: //***######***##%%%@@@@@@@%%%%#*#%%##%%%#**#%%*====--:-::----=***++==+++===------:.....::-----==========--------::::::::::--+%%@%##%%%%%%##%%*++**+==---:::: //**######***###%%@@@@@@@@%%%%######%%%%%%%%%#+---:::::::::--=+========-----:---::.....::----:----========----:::::::::::::-=#%%%#%%##%%%##%#****#*+==-::::: //**#######**###%@@@@@@@@%%%%%%##**##%%%%%%%##+=-::....::::-------------::::::-:::......::-:::::::::::-:::::::::::::::::::::-+%%%%%%%%%%#%%#*####%%%%#=-:::: //**######***###%@@@@@@@@%%%%%%%#**####%##%%%#*=::........:::::::::::::::::::::::.......:::::::::::::::::::::::::::::::::::::=%%%%%%%###%%####%%@@@@@@@*=--- //**#######**###%@@@@@@@@%%%%@%%%#***+*####%%%*=:...........:::::::::::::::::::::.......:::::::::::::::::::::::::::::::::::::=#%%#%%%%#####%%%%@@@@@@@@@@%%@ //**#######**##%%@@@@@@@@%%%%%%@@%##*##**#####*-:..................:::::::::::::.........::::::::::::::::::::::::::::::::::::-#%#*%##%####%@@@@@@@@@@@@@@@@@ //**#######**###%@@@@@@@@%%%%@@@@@@%####******+:::....................:::::::::...........::::::::::..:::::::.:::::::::::::::-*+=*%##%##%%%@@@@@@@@@@@@@@@@@ //**###*##***###%@@@@@@@%%%%%@@@@@@@%%###**++*+::..................::::::-::::.............::::::-::::::::::::::::::::.::::::-+===*#####@@@@@@@@@@@@@@@@@@@@ //+**********###%@@@@@@@@%%%%@@@@@@%%%##***+=++::...............:::::::--::................::...::---::::::::::::::::::.:::::-+=-=#####%@@@@@@@@@@@@@@@@@@@@ //+**********###%@@@@@@@%%%%%%@@@@@@%###%##*==+:::::.......::::::::::---:.....::.......:::::::...::----::::::::::::::::::::::-+=*%%%%%%#@@@@@@@@@@@@@@@@@@@@ //+**********###%@@@@@@@%%%%%%@@@@@@@%%%%#**+++-::::..:::::::::::::-----::::::::::::::::::::::::::---=----:::::::::::::::::::-*=*@%@@@@%%@@@@@@@@@@@@@@@@@@@ //****####***##%%@@@@@@@%%%%%%@@@@@@@@%%%##*++*=::::::::::::::::::----------==-------:-----=++=-------==----:::::::::::::::::+++%@@@@@@@@@@@@@@@@@@@@@@@@@@@ //.......::---=++*###%%%####*####%%%%%%%%#%#+=**:::::::::::::-------------==+****==-----=+++=====------===----::::::::::::::-*+#@@@@@@@@@@@@@@@@@@@@@@@@@@@@ //..............................::::::::::::-=**=::::::-------------------==+===++++======--==----:::---===-------::::::::::+###@@@@@@@@@@@@@@@@@@@@@@@@@%%* //...........................................:-==:::::----------------::::--========+++===-------:::::---====-------:::::::=###+*####%%%%%%%@@@@@@@@@@@%*==- //............................................::.:::::----------------::::::----========-------::::::::----==------:::::::-*%##*=---------===--::::::::::::: //............................................::::-:::----------------::::::::::::---------:::::::::::::----=------::::::-*%%###+-::....:::::::.........:::: //::::::::::::::..::..:...:::..................:.:+=::-------------=--:::::::::-================--:::::::--------::::::::=%@%###*=::......................:: //------------------------------------::::::::.::-*%=--------------------=++++***++***++++*+=+*++*+++=---:-----::::::::--#####%##+::.......:::...........::: //********++++***###******+++++++++++++++==-:::::-*%%=--------------==#%%*===--=-:::--::::-::-::---+#%*-------:::-------#%%#*****+-:::.:...::::::::::::::::: //###########%%%@@@@@@@@@@@%%%%%%%%@@@@@@%*+=-:::--=**=-------------=+#@%%%%%*=+=:::--::.::::--:+#%@@#=---:--:::-------#%####***+==-:::::::::::::::::::::::: //--===+=++++++***####%###########%%%%%%%%#+=-:::.::------------------+%@%%@@@@@%%%%%%####%%%@@@@@@%*=----::::--------=@%*****++==+==------::::::::::::::::: //-----------======++====-========++++++++==-:::..:--::----------------+#%%%@@@@%####%%###%%%@@@@@#+=::::::-----------+@%#+*###*+==++========---::::::------ //::-----------=======-------============-:.....::::.:-=+=----------:---=+#%@@@@%##########%%@@@%*+=-::::::::---------*@%#**####*+==+++++===++++==-----===== //::-==--------==-===-------==+====+++=:......:::::.::-+*#=---------:::---=#@@@@%##*########%@@%+==-:::::::::---------%@##***#%##*+========+==+*****+==----- //--*#########%@@@@@@@+=====*#%%#*=-:...:::::::::::.:-=+*%#=--------:::--=--+#@@%#**####**##%%*+==-::::::::::--------=%%##***#%%##*=+**+***+++=-::-==++++++= //--*#**#######%@@@@@@#-======-::::...::===-::::::::--==+#@%=------:::::----:-+#%##**##*###*+====-::::::::::::::-----*@%##***#%%%##+=+*+*******++*#*+=------ //--*####****%%@@%*=:.:--::::::..:::::--=++-::::::::-=-=+#@@%=-----::::::-=-----=+*####*=--==-==-::::::::::::::-----+%@%##***#%%%%##++**###****#*+*#%%%%##*+ //--*######*=:::-=+##*-::......:--:-====+++=-::::::-=--=*%@@@%=----:::::::-===--------------===-::::::::::::::----==*@@%##**##%%%%%#*+++*#########*+++==++++ //--*%#=:.-+#%%##*=:......::.:--:::-----=++=-:::::-----+#@@@@@%=---:::::::--=+===--------==++=--:::::::::::::---===+%@@%##**##%%%%%##******###***##**###*+== //=+:.:+#%###*#+:.......::::-=-:::::::--==+=-:::::----=*%@@@@@@#=--::::::----=+++++++++++++=----::::::::::::--====+#@@@%##**###%%%%##*********+++*%%*=*%@@@@ //.:*%%%####+:...:::......-+-::::::--::-====-::::-----+#@@@@@@@@#=-:::::::-----===+++===-------::::::::::::--====+*%@@@%######%%%%%%##*##*****+**#*#%%*=*+=+ //%%%%%%#=...:-::...-::.=%=.:--::::-::::-===-::::=-:-=#%@@@@@@@@%*=-::::::::-=----==-==--------:::::::::::--====++#@@@%#######%%%%%%##*#****+***#%%##%%*+#%# //@%@%-.::::...:+%@*:.+%-.:--------:::::-===-:::-=---+%%@@@@@@@@%#**-::::::::---=-=------------:::::::::-======++#@@@@%#######%%%%%%%##********##%%%###%%=+% //+:.......=%%+:....=%+.:==----------::--===-:::----=#%%@@@@@@%%%%*+*=::::::::---------------:::::::::-=======++*%@@@@#######%%%%%%%%%#*******##%%%###**#%#- //::..-*%*-......:*%=.:=+------------:::-===--:-----*#%@@@@@@%%%%%%**++=:::::::::----------::::::::::-=======++*#@@@@@#######%%%%%%%%%%#******#%%%#####%#*#% //:*%#-........-#%=..-==-------------:::====-------=*#%@@@@@%%%%%%%#*++++=--::::::---------:::::::--=+++===+++*#%@@@@%#######%%%%%%%%%%###***##%%%########*+ //+:........:=%%=::--===------------:::-===-----=-=+#%%@@@@@%%%%#####*+++++=---------------------===+++++++++*#%%@@@@%######%%%%%%%%%%#%%%###%%%%%#########* //.......:+#%%+:----===--:::-------::::--------===++#%%@@@@@%#########*++++*++===------==========+++++++++++**#%%%@@%######%%%%%%%%%%###%%%%%%@%%%##******** //:...::*@%#+:::--==---:::::------::::::-----=====+*#%%@@@@@%##########*++++****+++++++++++++++++++++++++++**#%%%%@@%####%%%%%%%%%%%%###%%%%%%%%%%##******** //...:#%-.::-:::----:::::::::::::::::::--=--====++**#%%@@@%%%###########*+=+++**++++++++++++++++++++++++++**##%##@@@%%%%%%%%%%%%%%%%%###%%%%%%%%%##********* //:..::*@#-.:-=::::::::.::::::::::::::-----=====++*#%%@@@@%%%#############*++++***+++++++++++++++++++++++**##%%#%@@@%%%%%%%%%%%%%%%%###%%%%%%%%%####******#% //::::--%@@%-.:-+=::::......::::::::::---======++**#%%@@@@@%@*#######%#*##**+==+++*+*++++++++*******+++++**#%%##@@@@%%%%%%%%%%%%%%%%####%%%%%%%#********#%%+ //---==+#%%@@@=..-+=:......:::::::::::-==-===+++**#%%%@@@@@%@#*%#####%##***#*+===++++*************++++++**%%%#*%@@@@%%%%%%%%%%%%%######%%%%%%%##******#@#++* //==++*###%%@@@@=..:-+-:.:.::::::::::-==-==+++++**#%%@@@@@@@@@*%######%#******+==++++++++****++++++++++**%%%#*#@@@@@%%%%%%%%%%%########%%%%%###*****%@#++*%@ #include <bits/stdc++.h> using namespace std; #define ll long long ll n,u,v,f[500005],par[500005],h[500005],k,ans,d[500005]; vector<ll>a[500005],vc[500005]; ll getlab(ll i) { if(f[i]<0) return i; return f[i]=getlab(f[i]); } void connect(ll u,ll v) { u=getlab(u); v=getlab(v); if(u==v) return; f[u]+=f[v]; f[v]=u; return; } void dfs(ll x,ll pa) { par[x]=pa; for(ll it:a[x]) if(it!=pa) { h[it]=h[x]+1; dfs(it,x); } } void collab(ll x,ll y) { x=getlab(x); y=getlab(y); while(x!=y) { if(h[x]<h[y]) swap(x,y); connect(par[x],x); x=getlab(par[x]); } return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>k; for(int i=1;i<=n;i++) { f[i]=-1; cin>>u>>v; a[u].push_back(v); a[v].push_back(u); } for(int i=1;i<=k;i++) { cin>>u; vc[u].push_back(i); } dfs(1,0); for(int i=1;i<=k;i++) for(int j=1;j<vc[i].size();j++) collab(vc[i][0],vc[i][j]); for(int i=1;i<=n;i++) for(ll it:a[i]) if(getlab(i)!=getlab(it)) d[i]++; for(int i=1;i<=n;i++) if(d[i]==1) ans++; cout<<(ans+1)/2; }
#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...