Submission #1261424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261424		duccnamm	Mergers (JOI19_mergers)	C++20	0 / 100	3095 ms	327680 KiB

mergers

//********###############***************+*******#####################*********************###**************#######****************+++++++****************+++
//********##############*****************+******#################**##*******++*******************+*+*******#######****************+++++++++***************++
//*******###############*****************+******#################**#********++******+***********+*++********#*####****************+++++++++***************++
//******###############*************************###*#############***#*******++******+***********+++++++****************************++++++++***************++
//*****#################************************##**##***#######****#*****+*++******+*+****+++====+++*******************************+++++++***************++
//*****##################***********************###*******#######*****+++++++=*****+=*+++++*++++==------==+++***********************++++******************++
//*******################********##************####*******#*###******+++++++==+****+-+-=+==-::..........:::::--+*****************************************+++
//**+*******#############*****#*####***********######****###*+-:..:.......::--=--=+=:+*=-::..........::::::::::::-+*************************************++++
//+++++******########********##**###***********#*#***###+-...::::::::::::::::::::::::::::..........::::::::::::-:::-=***#********************************+++
//+++++******########************##************##**#+-....::...::::::.::::::---:::::::::........:...::::--==----:::::::=*#**********************************
//+++++******#######**************#***************-..........::::::::----------=+=-::---:::::::::::::::::::--=++++==-::::-+=+*******************************
//++++******######**********#*************++++=:..........:::::::::::::::::::-===+-:+--:::::.........::-----:----==+*+-::-+**++**************+++**++******
//*+++*******#####***********#***********++++=:.:......::::--::::::::::::------=**++#*=-==----:::::::.::.:::-==-------=++-:::+*+++***********++++++++++**+++
//**++*******######********##*************+-::::....:::::-=::::::::::-----=-===:*#+#%*+*+==-----:::::::::-=-::--==-:----=+*=::-+++++*********+++++++++++++++
//**++*+******#####*********##**********+:::::::::---:-==::::::::-:----====+=+++++*%+=#*+++=----:::::::::::-==----==-------+*+:.-+++********++++++++++++++++
//**+++++*****#####******************#+-:-----:-=--:-==::::::::::---===+*###**+***#*=*#*==----:::::.::::-=----+=:=:-===--===-**=::+*++******++++++++++++++++
//***++++*****#####*****#######*****=::-------=+--=+-::::::::::-:--==+*###%%%##%#+#*-**=-------===-::::::---=-+*+-==:-=+=-=++-=**-.-++*+**++++++++++++++++++
//***+*******######****#########**+::----==-=++-=*+:--:::::::::--===+**+*=#%%%%%##%+=#+--+###+=:----::::---:-=-+*++++---=+==++=-+*+::++*++++++++++++++++++++
//**+*******#######***#########**+:---=++--++=-+*+---:::::::::-====++*#%%%*@%%%%*%#==+++*===+*##+--=::-+-----=+-+*+**+=-==+===+=-=*+::++++++++++++++++++++++
//*+++******#######***#######***+::--=+=-=++=+*+=:--::::::::-----=+++*#%%%*%%%#*#%#==+==----:::-=--+*--=+==-==+==*****+=-=++===++=-++-:=++++++++++++++++++++
//+++++****######******####****-::-==++=++++**+=-=-::--:::---:--==******#######*#%#=+***++=-::::::--====+====+++==***+++===+++==++===+=-==++++++++++++++++++
//++++++***######************+-:--=+++==+++**++==-::--------:--==++**########****#*+*#****#*+=--::----==++==+++++=+*#**+++==+===++====+=--==++++++++++++++++
//++++++***######*********++=:---=+===++++***++==---==---=:-:--=+++#%%%%%%%%%%#*++*###########+===----===++=++++++=+###**++==++==++====+=-===+*+++++++++++++
//+++++****#######*******++----===+==++++***++++--====--===---==***%%@@@@@%%@%##***###%%%%%%%%#*=====-====+++++**++=+#%#*#*+==++==++===++==++==*****++++****
//+++++****#######******++--====+++++**++****++=-=*==--===+--==+#%%@@@@@@%%%%%%#**####%%%%%%%%%#+=+++===++++++*+**+++*#####*+==+==++====++==++==+##*********
//++++*****########******-=====++++++*****+**++==*+==--==++-==+#%@%@@@@@%%%%%%###*#####%%%%%%%%%*++++=+=+++++++*+**+++*#####*+=====++====*+=-===--=****##***
//++++****#########*****==+++=+++++++*******++=+**++=-=++++=++#%%%@@@%%%####*******####%###%%%%#*++*++++++++*++++**+++*#%%###*+====+++===+++=-------+*******
//++++*****#########****=++++=+++*+********++++*++++===+++=+*#%%%%%%###*+++++++====++********###*****++++*+***++*****++*%%###**=====+++=+=+++==-----=*##****
//++++*****#########**#+=+++++**++**********+++*++*===+*+++**#%%####***+=====--------=====++******#*++****++*#*+*****++*#%%#%#*+==+=+++=+==++==----=+****#**
//+++*****##########**#+++++++++*****#*****+++*++++===+++++*##%%###**+===------:::::----====+++*****++*******#*++**+****###%##**+=+==++=++++++=====+++====-:
//****########*#######*++++++++****##+*****++**++*++++++=+***####**++=------::::::::::-----===++****+********##++##**#**##%%##**+=++=+*++++++++======----:::
//****################*+*++*++******+******++*++**++++**+**#*****+++==---::::::::::::::::----===++******#****##**##**##*##%%%#***+++=+*++++++=+=--==-::::::.
//***########*####%%%%#+*+*+++*******##*##*++*++**++*******#****+++===---:::::::::::::::::----==++****#*##*##*##*###*##**#%%%%#**+++++**+++*++==-:-=-::.....
//***########*###%%%@@%+#****+**+***###*#**+**+****+*******#****++====--::::::::::::::::::::---==+**#***############**#**#%%%%*#*++*+***++*#*++=-:.:-:......
//****######**##%%@@@@@*#****++****######******#***+**+****#***++===-----:::::::.....:.::::---==+**##*####################%%%%##*++*****+++##*++-::.:-:.....
//****##*###**##%%@@@@@*#**++***#*###*###****###********#***#**++====-----:::::::::::::::-----=++*###*####################%%%###*++*****+++*#*++=::..::.....
//*******#######%%@@@@@%*#*+++****#*#####****######**#*##***#*+====-----:::::::::...::::::---===+*########%####%##########%%####*++*#****++*#**++-.....:....
//*******###*###%%@@@@@%#*+**+*#*###%%###**#############****##*++========------::::::::::::----=+*#######%%%###%#######%%#%%####*++##********##*+=..........
//********######%%@@@@@%%****+*#*########**#####*########*+*#*+=-----:::::::::::::::::::::::---+*##**#*####%###%#######%%#%%####*+*###*#******#*++:...::::::
//********##*###%%@@@@@%@#***+***#%#%%%%#**######%%#####**+***+==------::::::::::::..::::::::-=*###**#*########%######%%%#%%%%##***#%#*********#*+-..:::::::
//********###*##%%@@@@@@@%#**+***##%%%%%#**#####%%#######***###********+==-::::::::::::::::::-*######%#%%%%%%%%%%#####%%%#%%%%##***%%#*****##*+***=:::::::::
//*******###**##%@@@@@@@@%*#*****###%%%%*#*#####%%%#######*########%%%###+===-:::::::::::::--=*#%%%%%%%%%%%%%%%%%%#####%%%%%%%##***%%#*****##*++*++:::::::::
//*******#######%%@@@@@@@####*+**###%%%%####%##%%%%#########*##****+*++++=====-::::::::::--=+**##%%%%%%%%%###%%%%#######%%%%%%##**##%#*#***##**++**-::::::::
//***#######*###%%@@@@@@%%##*++**###%@%%#%##%#%%#%####*#%###++**+++=====----=--:::::::::--==+++**#%###%%%##*###%%%######%%%%%%#**###%%##***###*++**-::::::::
//***#######*###%%@@@@@@%%%#*++*+##%%%%#*#####%%%%#*****####*=+*++++=====------:::::::::---======+*####%%%#**#####**#####%%%%%#####%%%##**#####*=+*-:-------
//**########*##%@@@@@@@%%%##++*+###%%%####%%%%%%%###**++**##*+**+++=========---::::::::------====+++**#%%%%%#####***####%%%%%#####%%%##*######*=*:--------
//***#######**##%@@@@@@@%%%%#*+***##%%%#%#%%%%%%%%#***+==+#*##*****+++===++===---::::::------========+++**#####%%##*****##%%%%#####%%%##**#%%##*+*=:::------
//***#######**##%@@@@@@@%%%%#*****##%%%%%#%%%%#%%%#**++=-=**####*#*+++++++++++==--:::::---=======+++++++****+++++*##******%%%####%#%%%##*##%%##*++::::------
//***######***##%@@@@@@@@@%%%*****######%%%%%%#%%##**++===+####%%%%%%%%#*++++++=--:::::---==++++++*%%@@%%##*+++====+**++++*%%%%##%%%%%##*#%%%%#*+-:-:-------
//***######**###%@@@@@@@%@%%%#**#**##%%%@#%%#%%%##**+====++*##%#*#%%%*##***+++++=-::::::--=++++*#*+#%#*#*=+#**++=----=====+#%%%%#%%%%%####%%%##+=-----====--
//***######**###%%@@@@@@%@%%%#**###*%##%%###%%%##*++=======+**##**#%%%#++*##==++=-::..::-==+==*#*+=#%###*+*++++==--------==+#%%%%#%%%####%#%%#*==-=-======-:
//***######**###%%%@@@@@@@%%%%**%%%######*####**++==--------=+***++=======----==-::....:--======+++++====-----------:::::--=*%%%%##%%%%%%%#%%#+=+=====----::
//***######***##%%%@@@@@@@%%%%#*#%%##%%%#**#%%*====--:-::----=***++==+++===------:.....::-----==========--------::::::::::--+%%@%##%%%%%%##%%*++**+==---::::
//**######***###%%@@@@@@@@%%%%######%%%%%%%%%#+---:::::::::--=+========-----:---::.....::----:----========----:::::::::::::-=#%%%#%%##%%%##%#****#*+==-:::::
//**#######**###%@@@@@@@@%%%%%%##**##%%%%%%%##+=-::....::::-------------::::::-:::......::-:::::::::::-:::::::::::::::::::::-+%%%%%%%%%%#%%#*####%%%%#=-::::
//**######***###%@@@@@@@@%%%%%%%#**####%##%%%#*=::........:::::::::::::::::::::::.......:::::::::::::::::::::::::::::::::::::=%%%%%%%###%%####%%@@@@@@@*=---
//**#######**###%@@@@@@@@%%%%@%%%#***+*####%%%*=:...........:::::::::::::::::::::.......:::::::::::::::::::::::::::::::::::::=#%%#%%%%#####%%%%@@@@@@@@@@%%@
//**#######**##%%@@@@@@@@%%%%%%@@%##*##**#####*-:..................:::::::::::::.........::::::::::::::::::::::::::::::::::::-#%#*%##%####%@@@@@@@@@@@@@@@@@
//**#######**###%@@@@@@@@%%%%@@@@@@%####******+:::....................:::::::::...........::::::::::..:::::::.:::::::::::::::-*+=*%##%##%%%@@@@@@@@@@@@@@@@@
//**###*##***###%@@@@@@@%%%%%@@@@@@@%%###**++*+::..................::::::-::::.............::::::-::::::::::::::::::::.::::::-+===*#####@@@@@@@@@@@@@@@@@@@@
//+**********###%@@@@@@@@%%%%@@@@@@%%%##***+=++::...............:::::::--::................::...::---::::::::::::::::::.:::::-+=-=#####%@@@@@@@@@@@@@@@@@@@@
//+**********###%@@@@@@@%%%%%%@@@@@@%###%##*==+:::::.......::::::::::---:.....::.......:::::::...::----::::::::::::::::::::::-+=*%%%%%%#@@@@@@@@@@@@@@@@@@@@
//+**********###%@@@@@@@%%%%%%@@@@@@@%%%%#**+++-::::..:::::::::::::-----::::::::::::::::::::::::::---=----:::::::::::::::::::-*=*@%@@@@%%@@@@@@@@@@@@@@@@@@@
//****####***##%%@@@@@@@%%%%%%@@@@@@@@%%%##*++*=::::::::::::::::::----------==-------:-----=++=-------==----:::::::::::::::::+++%@@@@@@@@@@@@@@@@@@@@@@@@@@@
//.......::---=++*###%%%####*####%%%%%%%%#%#+=**:::::::::::::-------------==+****==-----=+++=====------===----::::::::::::::-*+#@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//..............................::::::::::::-=**=::::::-------------------==+===++++======--==----:::---===-------::::::::::+###@@@@@@@@@@@@@@@@@@@@@@@@@%%*
//...........................................:-==:::::----------------::::--========+++===-------:::::---====-------:::::::=###+*####%%%%%%%@@@@@@@@@@@%*==-
//............................................::.:::::----------------::::::----========-------::::::::----==------:::::::-*%##*=---------===--:::::::::::::
//............................................::::-:::----------------::::::::::::---------:::::::::::::----=------::::::-*%%###+-::....:::::::.........::::
//::::::::::::::..::..:...:::..................:.:+=::-------------=--:::::::::-================--:::::::--------::::::::=%@%###*=::......................::
//------------------------------------::::::::.::-*%=--------------------=++++***++***++++*+=+*++*+++=---:-----::::::::--#####%##+::.......:::...........:::
//********++++***###******+++++++++++++++==-:::::-*%%=--------------==#%%*===--=-:::--::::-::-::---+#%*-------:::-------#%%#*****+-:::.:...:::::::::::::::::
//###########%%%@@@@@@@@@@@%%%%%%%%@@@@@@%*+=-:::--=**=-------------=+#@%%%%%*=+=:::--::.::::--:+#%@@#=---:--:::-------#%####***+==-::::::::::::::::::::::::
//--===+=++++++***####%###########%%%%%%%%#+=-:::.::------------------+%@%%@@@@@%%%%%%####%%%@@@@@@%*=----::::--------=@%*****++==+==------:::::::::::::::::
//-----------======++====-========++++++++==-:::..:--::----------------+#%%%@@@@%####%%###%%%@@@@@#+=::::::-----------+@%#+*###*+==++========---::::::------
//::-----------=======-------============-:.....::::.:-=+=----------:---=+#%@@@@%##########%%@@@%*+=-::::::::---------*@%#**####*+==+++++===++++==-----=====
//::-==--------==-===-------==+====+++=:......:::::.::-+*#=---------:::---=#@@@@%##*########%@@%+==-:::::::::---------%@##***#%##*+========+==+*****+==-----
//--*#########%@@@@@@@+=====*#%%#*=-:...:::::::::::.:-=+*%#=--------:::--=--+#@@%#**####**##%%*+==-::::::::::--------=%%##***#%%##*=+**+***+++=-::-==++++++=
//--*#**#######%@@@@@@#-======-::::...::===-::::::::--==+#@%=------:::::----:-+#%##**##*###*+====-::::::::::::::-----*@%##***#%%%##+=+*+*******++*#*+=------
//--*####****%%@@%*=:.:--::::::..:::::--=++-::::::::-=-=+#@@%=-----::::::-=-----=+*####*=--==-==-::::::::::::::-----+%@%##***#%%%%##++**###****#*+*#%%%%##*+
//--*######*=:::-=+##*-::......:--:-====+++=-::::::-=--=*%@@@%=----:::::::-===--------------===-::::::::::::::----==*@@%##**##%%%%%#*+++*#########*+++==++++
//--*%#=:.-+#%%##*=:......::.:--:::-----=++=-:::::-----+#@@@@@%=---:::::::--=+===--------==++=--:::::::::::::---===+%@@%##**##%%%%%##******###***##**###*+==
//=+:.:+#%###*#+:.......::::-=-:::::::--==+=-:::::----=*%@@@@@@#=--::::::----=+++++++++++++=----::::::::::::--====+#@@@%##**###%%%%##*********+++*%%*=*%@@@@
//.:*%%%####+:...:::......-+-::::::--::-====-::::-----+#@@@@@@@@#=-:::::::-----===+++===-------::::::::::::--====+*%@@@%######%%%%%%##*##*****+**#*#%%*=*+=+
//%%%%%%#=...:-::...-::.=%=.:--::::-::::-===-::::=-:-=#%@@@@@@@@%*=-::::::::-=----==-==--------:::::::::::--====++#@@@%#######%%%%%%##*#****+***#%%##%%*+#%#
//@%@%-.::::...:+%@*:.+%-.:--------:::::-===-:::-=---+%%@@@@@@@@%#**-::::::::---=-=------------:::::::::-======++#@@@@%#######%%%%%%%##********##%%%###%%=+%
//+:.......=%%+:....=%+.:==----------::--===-:::----=#%%@@@@@@%%%%*+*=::::::::---------------:::::::::-=======++*%@@@@#######%%%%%%%%%#*******##%%%###**#%#-
//::..-*%*-......:*%=.:=+------------:::-===--:-----*#%@@@@@@%%%%%%**++=:::::::::----------::::::::::-=======++*#@@@@@#######%%%%%%%%%%#******#%%%#####%#*#%
//:*%#-........-#%=..-==-------------:::====-------=*#%@@@@@%%%%%%%#*++++=--::::::---------:::::::--=+++===+++*#%@@@@%#######%%%%%%%%%%###***##%%%########*+
//+:........:=%%=::--===------------:::-===-----=-=+#%%@@@@@%%%%#####*+++++=---------------------===+++++++++*#%%@@@@%######%%%%%%%%%%#%%%###%%%%%#########*
//.......:+#%%+:----===--:::-------::::--------===++#%%@@@@@%#########*++++*++===------==========+++++++++++**#%%%@@%######%%%%%%%%%%###%%%%%%@%%%##********
//:...::*@%#+:::--==---:::::------::::::-----=====+*#%%@@@@@%##########*++++****+++++++++++++++++++++++++++**#%%%%@@%####%%%%%%%%%%%%###%%%%%%%%%%##********
//...:#%-.::-:::----:::::::::::::::::::--=--====++**#%%@@@%%%###########*+=+++**++++++++++++++++++++++++++**##%##@@@%%%%%%%%%%%%%%%%%###%%%%%%%%%##*********
//:..::*@#-.:-=::::::::.::::::::::::::-----=====++*#%%@@@@%%%#############*++++***+++++++++++++++++++++++**##%%#%@@@%%%%%%%%%%%%%%%%###%%%%%%%%%####******#%
//::::--%@@%-.:-+=::::......::::::::::---======++**#%%@@@@@%@*#######%#*##**+==+++*+*++++++++*******+++++**#%%##@@@@%%%%%%%%%%%%%%%%####%%%%%%%#********#%%+
//---==+#%%@@@=..-+=:......:::::::::::-==-===+++**#%%%@@@@@%@#*%#####%##***#*+===++++*************++++++**%%%#*%@@@@%%%%%%%%%%%%%######%%%%%%%##******#@#++*
//==++*###%%@@@@=..:-+-:.:.::::::::::-==-==+++++**#%%@@@@@@@@@*%######%#******+==++++++++****++++++++++**%%%#*#@@@@@%%%%%%%%%%%########%%%%%###*****%@#++*%@
#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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30